【6*】差分约束系统学习笔记

前言

此类知识点大纲中并未涉及，所以【6】是我自己的估计，后带星号表示估计，仅供参考。

差分约束系统属于图论建模，有一定的思维难度，而且比较绕，同时题目中的隐含条件也非常多，是一个比较难的知识点。

差分约束

给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：

$$\{\begin{array}{l}{x}_{c_1}-x_{c_1^{\prime }}\le y_1\\ x_{c_2}-x_{c_2^{\prime }}\le y_2\\ \cdots \\ x_{c_m}-x_{c_m^{\prime }}\le y_m\end{array}$$

的不等式组，求任意一组满足这个不等式组的解（或 $x_i-x_j$ 的最大值）。

变形得到：

$$\{\begin{array}{l}{x}_{c_1}\le y_1+x_{c_1^{\prime }}\\ x_{c_2}\le y_2+x_{c_2^{\prime }}\\ \cdots \\ x_{c_m}\le y_m+x_{c_m^{\prime }}\end{array}$$

此时，$x_i$ 最大可以取 $x_{i^{\prime }}+y_i$ ，于是可以把这个看作一条 $i^{\prime }\to i$ ，边权为 $y_i$ 的有向边，这样边上存储的就是 $i^{\prime }\to i$ 的最大差值。这样建成一张有向图后，每条 $i\to j$ 的路径就是 $x_i$ 与 $x_j$ 的在一个不等式组中的最大差值。根据不等式“同小取小”的原则，$x_i$ 与 $x_j$ 的最大差值就是 $i\to j$ 的最短路径，可以直接使用SPFA求解。

一个差分约束系统会有 $3$ 种情况：

$1$ ：有负环，证明没有最小值，该差分约束系统无解。

$2$ ：在没有负环的情况下，点 $i$ 和点 $j$ 不连通，之间没有约束，该差分约束系统有无数解。

$3$ ：无负环的连通图，有解。

不等式的统一见例题 $2$ 。

差分约束例题

例题 $1$ ：

P5960 【模板】差分约束算法

差分约束模板题，可以建立一个“超级源点”，跑出一组差量直接输出即可。

或者看看 零碎知识点整理 的图论 $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$ ：

P1993 小 K 的农场

三种情况换算一下就是这样的：

$1$ ：$a-b\ge c$

两边同时除以 $-1$ ，得 $b-a\le -c$ 。

$2$ ：$a-b\le c$

$3$ ：$a=b$

可以化为 $a-b\le 0$ 且 $a-b\ge 0$ ，再选择一个不等式反转就行。

建立一个差分约束系统，在“超级源点”处跑一边SPFA。如果有负环，证明没有最小值，该差分约束系统无解，输出 No ，否则输出 Yes 。

注意一下两点：

$1$ ：SPFA的队列数组一定要足够长。

$2$ ：由于添加了一个“超级源点”，每个点的最多入队次数是 $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$ 个不等式，有 $n$ 个未知数的形如：

$$\{\begin{array}{l}{x}_{c_1}-x_{c_1^{\prime }}\ge y_1\\ x_{c_2}-x_{c_2^{\prime }}\ge y_2\\ \cdots \\ x_{c_m}-x_{c_m^{\prime }}\ge y_m\end{array}$$

的不等式组，求任意一组满足这个不等式组的解（或 $x_i-x_j$ 的最小值）。

变形得到：

$$\{\begin{array}{l}{x}_{c_1}\ge y_1+x_{c_1^{\prime }}\\ x_{c_2}\ge y_2+x_{c_2^{\prime }}\\ \cdots \\ x_{c_m}\ge y_m+x_{c_m^{\prime }}\end{array}$$

此时，$x_i$ 最小可以取 $x_{i^{\prime }}+y_i$ ，于是可以把这个看作一条 $i^{\prime }\to i$ ，边权为 $y_i$ 的有向边，这样边上存储的就是 $i^{\prime }\to i$ 的最小差值。这样建成一张有向图后，每条 $i\to j$ 的路径就是 $x_i$ 与 $x_j$ 的在一个不等式组中的最小差值。根据不等式“同大取大”的原则，$x_i$ 与 $x_j$ 的最小差值就是 $i\to j$ 的最长路径，可以直接使用SPFA或拓扑排序求解。

差分约束扩展例题

例题 $3$ ：

UVA1723 Intervals

由于本题涉及到区间计数，自然联想到前缀和。又因为题目要求最小化取的数字的个数，那么就是要化出带 $\ge$ 的式子。

设 $s_i$ 为前 $i$ 项的前缀和（选择的数字个数），那么对于区间 $[a,b]$ 中至少取任意互不相同的 $c$ 个整数，则根据前缀和思想，转化为：

$$s_b-s_{a-1}\ge c$$

同时，这题有两个隐含条件：

$1$ ：$s_i-s_{i-1}\ge 0$

后面的前缀和一定比前面大，因为数字要么选，要么不选，是一个 $+0$ 或 $+1$ 的变化，前缀和在这里只增不减。

$2$ ：$s_i-s_{i-1}\le 1$

因为每个数字只能选择一次，所以对于每个位置，前缀和每次最多只能增加 $1$ 。

变形后得到：$s_{i-1}-s_i\ge -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;
}

后记

弄了一句口诀，方便记忆：

最大小于最短路，最小大于最长路。