差分约束

差分约束系统

如果一个不等式组由 \(n\) 个变量和 \(m\) 个约束条件组成,形成 \(m\) 个形如 \(x_j-x_i\leq k\)\(i,j\in[1,n]\)\(k\) 为常数)的不等式,则称其为 差分约束系统。换句话说,解决差分约束问题就是求解一组变量的不等式组。

问题转化

对于 \(x_j-x_i\le k\),我们会发现它类似最短路网络中的三角不等式 \(d_v-d_u\le w_{<u,v>}\),那是否可以通过最短路的形式解决呢?显然是可以的。

我们首先把这个不等式化一下,成 \(x_j\le x_i+k\)。可以推出,\(x_j\) 的最大值只可能是 \(x_i+k\),最小不限。

那我们再次假设如果 \(x_j\)\(x_{i'}\)\(x_{i''}\)\(x_{i'''}\) 都有关,我们就可以得到三个不等式,即一个不等式组:

\[\begin{cases} x_j\le x_{i'}+b \\\ x_j\le x_{i''}+b \\\ x_j\le x_{i'''}+b \end{cases}\]

那么 \(x_j\) 满足所有不等式下的最大值应该是:

\[\min\{x_{i'}+b,x_{i''}+b,x_{i'''}+b\}\]

因为要满足所有不等式,所以必须要取最小值来满足所有的不等式。不等式解集应该是范围更小的那一个。

注意,我们上面提到的 \(i\) 都可以模拟成 \(j\)前继

那么我们可以再次简化模型。

假设有多个 \(x_i\)\(x_j\) 的前继,那么我们就可以得到一个式子,满足原不等式组的求解:

\[x_j=\min\{x_i+b\}\]

这不就是最短路嘛!

此时,可将每个变量看成一个顶点,并设一个超级源点 \(x_0\),它连向每个顶点(除了自身)且边权为 \(0\),这时再对每一个不等式 \(x_j-x_i\le k\) 连一条边权为 \(k\) 的有向边 \(<i,j>\),此时用 \(x_j\) 表示超级源点到 \(j\) 的最短路,用 \(x_i\) 表示超级源点到 \(i\) 的最短路,由于有边 \(<i,j>\) 存在,从而有 \(x_j\le x_i+k\),即为原不等式的变形。

在有解的情况下,跑一遍最短路,最短路的答案 \(d_i\) 正是原不等式组的一个解 \(x_i\)

使用“最长路”求解也是可以的。

连边方法

差分约束问题可以转化为最短路或最长路问题,所以两种转化也就形成了两种不同的连边方法。

  1. 连边后求最短路 将 \(x_j-x_i\le k\) 变形为 \(x_j\le x_i+k\),即从 \(i\)\(j\) 连一条边权为 \(k\) 的边。加入超级源点后求最短路,得到 \(x_i\le 0\) 所有 \(x\) 最大解。
  2. 连边后求最长路 将 \(x_j-x_i\le k\) 变形为 \(x_i\ge x_j-k\),即从 \(i\)\(j\) 连一条边权为 \(-k\) 的边。加入超级源点后求最长路,得到 \(x_i\ge 0\) 所有 \(x\) 最小解。

显而易见地,两种方法求出来的解大概率是不同的。

判断无解

若求最短路,图中存在负环,则该不等式组无解。

此时,即可放心大胆地 SPFA,只需在 SPFA 的同时用一个数组来记录每个顶点入队次数,如果一个顶点入队次数大于 \(n\),说明该图存在负环。对于 DFS_SPFA,只需看当前顶点如果访问过,说明该图存在负环。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
struct edge
{
int nxt,end,len;
}e[1000000+5];
int n,m,cnt=0,head[100000+5],vis[100000+5],dis[100000+5],in[100000+5];
long long ans=0;
queue<int>q;
void add(int a,int b,int len)
{
e[++cnt]=(edge){head[a],b,len};
head[a]=cnt;
}
int dfs_spfa(int now)
{
vis[now]=1;
for(int i=head[now];i;i=e[i].nxt)
{
int to=e[i].end;
if(dis[to]<dis[now]+e[i].len)
{
dis[to]=dis[now]+e[i].len;
if(vis[to]) return 1;
if(dfs_spfa(to)) return 1;
}
}
vis[now]=0;
return 0;
}
void bfs_spfa(int x)
{
q.push(x);
while(!q.empty())
{
int now=q.front();q.pop();
vis[now]=0;
for(int i=head[now];i;i=e[i].nxt)
{
int to=e[i].end;
if(dis[to]<dis[now]+e[i].len)
{
dis[to]=dis[now]+e[i].len;
if(!vis[to])
q.push(to),vis[to]=1;
}
}
}
return;
}
void yzmain()
{
int a,b,c;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,-c);
}
for(int i=1;i<=n;i++)
add(0,i,0);
for(int i=1;i<=n;i++)
if(dfs_spfa(i)) {printf("NO");return;}
bfs_spfa(0);
for(int i=1;i<=n;i++)
printf("%d ",dis[i]);
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}

例题

P6145 [USACO20FEB]Timeline G

https://www.luogu.com.cn/problem/P6145

连边方式:

1
2
3
4
for i from 1 to n
add < 0,i > = Si
for i from 1 to c
add < ai,bi > = xi

之后求最长路。

P4878 [USACO05DEC]Layout G

https://www.luogu.com.cn/problem/P4878

连边方式:

1
2
3
4
5
6
7
8
for i from 1 to ML
add < Ai,Bi > = Di
for i from 1 to MD
add < Bi,Ai > = -Di
for i from 1 to n
add < 0,i > = 0
for i from 2 to n
add < i,i-1 > = 0

之后求最短路。差分约束题还是有很多条件在里面的,仔细看题是正道。