前言
此类知识点大纲中并未涉及,所以【6】是我自己的估计,后带星号表示估计,仅供参考。
差分约束系统属于图论建模,有一定的思维难度,而且比较绕,同时题目中的隐含条件也非常多,是一个比较难的知识点。
差分约束
给出一组包含 m m m 个不等式,有 n n n 个未知数的形如:
{ x c 1 − x c 1 ′ ≤ y 1 x c 2 − x c 2 ′ ≤ y 2 ⋯ x c m − x c m ′ ≤ y m \begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} ⎩ ⎨ ⎧xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym
的不等式组,求任意一组满足这个不等式组的解(或 x i − x j x_i-x_j xi−xj 的最大值)。
变形得到:
{ x c 1 ≤ y 1 + x c 1 ′ x c 2 ≤ y 2 + x c 2 ′ ⋯ x c m ≤ y m + x c m ′ \begin{cases} x_{c_1}\leq y_1+x_{c'_1} \\x_{c_2}\leq y_2+x_{c'_2} \\ \cdots\\ x_{c_m} \leq y_m+ x_{c'_m}\end{cases} ⎩ ⎨ ⎧xc1≤y1+xc1′xc2≤y2+xc2′⋯xcm≤ym+xcm′
此时, x i x_i xi 最大可以取 x i ′ + y i x_{i'}+y_i xi′+yi ,于是可以把这个看作一条 i ′ → i i'\to i i′→i ,边权为 y i y_i yi 的有向边,这样边上存储的就是 i ′ → i i'\to i i′→i 的最大差值。这样建成一张有向图后,每条 i → j i\to j i→j 的路径就是 x i x_i xi 与 x j x_j xj 的在一个不等式组中的最大差值。根据不等式“同小取小”的原则, x i x_{i} xi 与 x j x_j xj 的最大差值就是 i → j i\to j i→j 的最短路径,可以直接使用SPFA求解。
一个差分约束系统会有 3 3 3 种情况:
1 1 1 :有负环,证明没有最小值,该差分约束系统无解。
2 2 2 :在没有负环的情况下,点 i i i 和点 j j j 不连通,之间没有约束,该差分约束系统有无数解。
3 3 3 :无负环的连通图,有解。
不等式的统一见例题 2 2 2 。
差分约束例题
例题 1 1 1 :
P5960 【模板】差分约束算法
差分约束模板题,可以建立一个“超级源点”,跑出一组差量直接输出即可。
或者看看 零碎知识点整理 的图论 1.5 1.5 1.5 。
#include <bits/stdc++.h>
using namespace std;
struct node
{int t,next,dis;
}e[10050];
int m,n,c,d,k,h[5010],dis[5010],tol[5010],que[800010],book[5010],head=1,tail=0,cnt=0;
void add_edge(int u,int v,int dis)
{e[++cnt].next=h[u];e[cnt].t=v;e[cnt].dis=dis;h[u]=cnt;
}bool spfa(int s)
{que[++tail]=s;book[s]=1;while(head<=tail){int now=que[head];book[que[head]]=0;for(int i=h[now];i;i=e[i].next){int t=e[i].t;if(dis[now]+e[i].dis<dis[t]){dis[t]=dis[now]+e[i].dis;if(!book[t])que[++tail]=t,tol[t]++,book[t]=1;}if(tol[t]>=n+1)return 1;}head++;}return 0;
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)add_edge(0,i,0);for(int i=1;i<=n;i++)dis[i]=99999999;for(int i=1;i<=m;i++){scanf("%d%d%d",&c,&d,&k);add_edge(d,c,k);}if(spfa(0))printf("NO\n");else {for(int i=1;i<=n;i++)printf("%d ",dis[i]);printf("\n");}return 0;
}
例题 2 2 2 :
P1993 小 K 的农场
三种情况换算一下就是这样的:
1 1 1 : a − b ≥ c a-b\ge c a−b≥c
两边同时除以 − 1 -1 −1 ,得 b − a ≤ − c b-a\le -c b−a≤−c 。
2 2 2 : a − b ≤ c a-b\le c a−b≤c
3 3 3 : a = b a=b a=b
可以化为 a − b ≤ 0 a-b\le0 a−b≤0 且 a − b ≥ 0 a-b\ge0 a−b≥0 ,再选择一个不等式反转就行。
建立一个差分约束系统,在“超级源点”处跑一边SPFA。如果有负环,证明没有最小值,该差分约束系统无解,输出 No
,否则输出 Yes
。
注意一下两点:
1 1 1 :SPFA的队列数组一定要足够长。
2 2 2 :由于添加了一个“超级源点”,每个点的最多入队次数是 n + 1 n+1 n+1 次。
#include <bits/stdc++.h>
using namespace std;
struct node
{int t,next,dis;
}e[20050];
int m,n,c,d,k,h[10010],dis[10010],tol[10010],que[16000010],book[10010],head=1,tail=0,cnt=0;
void add_edge(int u,int v,int dis)
{e[++cnt].next=h[u];e[cnt].t=v;e[cnt].dis=dis;h[u]=cnt;
}bool spfa(int s)
{que[++tail]=s;book[s]=1;while(head<=tail){int now=que[head];book[que[head]]=0;for(int i=h[now];i;i=e[i].next){int t=e[i].t;if(dis[now]+e[i].dis<dis[t]){dis[t]=dis[now]+e[i].dis;if(!book[t])que[++tail]=t,tol[t]++,book[t]=1;}if(tol[t]>=n+1)return 1;}head++;}return 0;
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)add_edge(0,i,0);for(int i=1;i<=n;i++)dis[i]=99999999;for(int i=1;i<=m;i++){int op=0;scanf("%d",&op);if(op==1){scanf("%d%d%d",&c,&d,&k);add_edge(c,d,-k);}else if(op==2){scanf("%d%d%d",&c,&d,&k);add_edge(d,c,k);}else if(op==3){scanf("%d%d",&c,&d);add_edge(d,c,0);add_edge(c,d,0);}}if(spfa(0))printf("No\n");else printf("Yes\n");return 0;
}
差分约束扩展
给出一组包含 m m m 个不等式,有 n n n 个未知数的形如:
{ x c 1 − x c 1 ′ ≥ y 1 x c 2 − x c 2 ′ ≥ y 2 ⋯ x c m − x c m ′ ≥ y m \begin{cases} x_{c_1}-x_{c'_1}\geq y_1 \\x_{c_2}-x_{c'_2} \geq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\geq y_m\end{cases} ⎩ ⎨ ⎧xc1−xc1′≥y1xc2−xc2′≥y2⋯xcm−xcm′≥ym
的不等式组,求任意一组满足这个不等式组的解(或 x i − x j x_i-x_j xi−xj 的最小值)。
变形得到:
{ x c 1 ≥ y 1 + x c 1 ′ x c 2 ≥ y 2 + x c 2 ′ ⋯ x c m ≥ y m + x c m ′ \begin{cases} x_{c_1}\geq y_1+x_{c'_1} \\x_{c_2}\geq y_2+x_{c'_2} \\ \cdots\\ x_{c_m} \geq y_m+ x_{c'_m}\end{cases} ⎩ ⎨ ⎧xc1≥y1+xc1′xc2≥y2+xc2′⋯xcm≥ym+xcm′
此时, x i x_i xi 最小可以取 x i ′ + y i x_{i'}+y_i xi′+yi ,于是可以把这个看作一条 i ′ → i i'\to i i′→i ,边权为 y i y_i yi 的有向边,这样边上存储的就是 i ′ → i i'\to i i′→i 的最小差值。这样建成一张有向图后,每条 i → j i\to j i→j 的路径就是 x i x_i xi 与 x j x_j xj 的在一个不等式组中的最小差值。根据不等式“同大取大”的原则, x i x_{i} xi 与 x j x_j xj 的最小差值就是 i → j i\to j i→j 的最长路径,可以直接使用SPFA或拓扑排序求解。
差分约束扩展例题
例题 3 3 3 :
UVA1723 Intervals
由于本题涉及到区间计数,自然联想到前缀和。又因为题目要求最小化取的数字的个数,那么就是要化出带 ≥ \ge ≥ 的式子。
设 s i s_i si 为前 i i i 项的前缀和(选择的数字个数),那么对于区间 [ a , b ] [a,b] [a,b] 中至少取任意互不相同的 c c c 个整数,则根据前缀和思想,转化为:
s b − s a − 1 ≥ c s_b-s_{a-1}\ge c sb−sa−1≥c
同时,这题有两个隐含条件:
1 1 1 : s i − s i − 1 ≥ 0 s_i-s_{i-1}\ge0 si−si−1≥0
后面的前缀和一定比前面大,因为数字要么选,要么不选,是一个 + 0 +0 +0 或 + 1 +1 +1 的变化,前缀和在这里只增不减。
2 2 2 : s i − s i − 1 ≤ 1 s_i-s_{i-1}\le1 si−si−1≤1
因为每个数字只能选择一次,所以对于每个位置,前缀和每次最多只能增加 1 1 1 。
变形后得到: s i − 1 − s i ≥ − 1 s_{i-1}-s_i\ge-1 si−1−si≥−1
#include <bits/stdc++.h>
using namespace std;
struct node
{int t,next,dis;
}e[800050];
int t,n,md,c,d,k,h[50010],dis[50010],tol[50010],que[21000010],book[50010],head=1,tail=0,cnt=0,maxn=0;
void add_edge(int u,int v,int dis)
{e[++cnt].next=h[u];e[cnt].t=v;e[cnt].dis=dis;h[u]=cnt;
}bool spfa(int s)
{que[++tail]=s;book[s]=1;while(head<=tail){int now=que[head];book[que[head]]=0;for(int i=h[now];i;i=e[i].next){int t=e[i].t;if(dis[now]+e[i].dis>dis[t]){dis[t]=dis[now]+e[i].dis;if(!book[t])que[++tail]=t,tol[t]++,book[t]=1;}if(tol[t]>=maxn)return 1;}head++;}return 0;
}int main()
{scanf("%d",&t);while(t--){memset(h,0,sizeof(h));memset(tol,0,sizeof(tol));memset(book,0,sizeof(book));head=1;tail=0;cnt=0;maxn=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&c,&d,&k);maxn=max(c,maxn);maxn=max(d,maxn);add_edge(c-1,d,k);}for(int i=1;i<=maxn;i++)dis[i]=-1;dis[0]=0;for(int i=1;i<=maxn;i++){add_edge(i-1,i,0);add_edge(i,i-1,-1);}spfa(0);printf("%d\n",dis[maxn]);if(t)printf("\n");}return 0;
}
后记
弄了一句口诀,方便记忆:
最大小于最短路,最小大于最长路。