6差分约束系统学习笔记
【6*】差分约束系统学习笔记
前言
此类知识点大纲中并未涉及，所以【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}
⎩
⎨
⎧
x
c
1
−
x
c
1
′
≤
y
1
x
c
2
−
x
c
2
′
≤
y
2
⋯
x
c
m
−
x
c
m
′
≤
y
m
的不等式组，求任意一组满足这个不等式组的解（或
x i − x j x_i-x_j
x
i
−
x
j
的最大值）。
变形得到：
{ 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}
⎩
⎨
⎧
x
c
1
≤
y
1
x
c
1
′
x
c
2
≤
y
2
x
c
2
′
⋯
x
c
m
≤
y
m
x
c
m
′
此时，
x i x_i
x
i
最大可以取
x i ′ + y i x_{i’}+y_i
x
i
′
y
i
，于是可以把这个看作一条
i ′ → i i’\to i
i
′
→
i ，边权为
y i y_i
y
i
的有向边，这样边上存储的就是
i ′ → i i’\to i
i
′
→
i 的最大差值。这样建成一张有向图后，每条
i → j i\to j
i
→
j 的路径就是
x i x_i
x
i
与
x j x_j
x
j
的在一个不等式组中的最大差值。根据不等式“同小取小”的原则，
x i x_{i}
x
i
与
x j x_j
x
j
的最大差值就是
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 ：
差分约束模板题，可以建立一个“超级源点”，跑出一组差量直接输出即可。
或者看看 的图论
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 ：
三种情况换算一下就是这样的：
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}
⎩
⎨
⎧
x
c
1
−
x
c
1
′
≥
y
1
x
c
2
−
x
c
2
′
≥
y
2
⋯
x
c
m
−
x
c
m
′
≥
y
m
的不等式组，求任意一组满足这个不等式组的解（或
x i − x j x_i-x_j
x
i
−
x
j
的最小值）。
变形得到：
{ 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}
⎩
⎨
⎧
x
c
1
≥
y
1
x
c
1
′
x
c
2
≥
y
2
x
c
2
′
⋯
x
c
m
≥
y
m
x
c
m
′
此时，
x i x_i
x
i
最小可以取
x i ′ + y i x_{i’}+y_i
x
i
′
y
i
，于是可以把这个看作一条
i ′ → i i’\to i
i
′
→
i ，边权为
y i y_i
y
i
的有向边，这样边上存储的就是
i ′ → i i’\to i
i
′
→
i 的最小差值。这样建成一张有向图后，每条
i → j i\to j
i
→
j 的路径就是
x i x_i
x
i
与
x j x_j
x
j
的在一个不等式组中的最小差值。根据不等式“同大取大”的原则，
x i x_{i}
x
i
与
x j x_j
x
j
的最小差值就是
i → j i\to j
i
→
j 的最长路径，可以直接使用SPFA或拓扑排序求解。
差分约束扩展例题
例题
3 3
3 ：
由于本题涉及到区间计数，自然联想到前缀和。又因为题目要求最小化取的数字的个数，那么就是要化出带
≥ \ge
≥ 的式子。
设
s i s_i
s
i
为前
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
s
b
−
s
a
−
1
≥
c
同时，这题有两个隐含条件：
1 1
1 ：
s i − s i − 1 ≥ 0 s_i-s_{i-1}\ge0
s
i
−
s
i
−
1
≥
0
后面的前缀和一定比前面大，因为数字要么选，要么不选，是一个
0 +0
0 或
1 +1
1 的变化，前缀和在这里只增不减。
2 2
2 ：
s i − s i − 1 ≤ 1 s_i-s_{i-1}\le1
s
i
−
s
i
−
1
≤
1
因为每个数字只能选择一次，所以对于每个位置，前缀和每次最多只能增加
1 1
1 。
变形后得到：
s i − 1 − s i ≥ − 1 s_{i-1}-s_i\ge-1
s
i
−
1
−
s
i
≥
−
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;
}后记
弄了一句口诀，方便记忆：
最大小于最短路，最小大于最长路。