差分约束系统
差分约束系统是一种特殊的 N N N元一次不等式组。它包含 N N N个变量 X 1 X_1 X1~ X N X_N XN以及 M M M个约束条件，每个约束条件都是由两个变量做差构成的，形如 X i − X j ≤ c k X_i-X_j\leq c_k Xi−Xj≤ck，其中 c k c_k ck是常数（可以是非负数，也可以是负数）， 1 ≤ i , j ≤ N , 1 ≤ k ≤ M 1\leq i,j\leq N,1\leq k\leq M 1≤i,j≤N,1≤k≤M。我们要解决的问题就是：求一组解 X 1 = a 1 , X 2 = a 2 , ⋯ , X N = a N X_1=a_1,X_2=a_2,\cdots,X_N=a_N X1=a1,X2=a2,⋯,XN=aN，即解 X = ( a 1 , a 2 , ⋯ , a N ) X=(a_1,a_2,\cdots,a_N) X=(a1,a2,⋯,aN)使得所有约束条件都能得到满足。
差分约束系统的每个约束条件 X i − X j ≤ c k X_i-X_j\leq c_k Xi−Xj≤ck可以变形为 X i ≤ X j + c k X_i\leq X_j+c_k Xi≤Xj+ck，这与单源最短路径问题中的三角不等式 d i s t [ y ] ≤ d i s t [ x ] + z dist[y]\leq dist[x]+z dist[y]≤dist[x]+z非常相似，注意这个式子是更新过后的。因此，我们可以把每个变量 X i X_i Xi看作是有向图中的一个节点 i i i，对于每个约束条件 X i − X j ≤ c k X_i-X_j\leq c_k Xi−Xj≤ck，从节点 j j j向节点 i i i连一条长度为 c k c_k ck的有向边。
引理：
设 X = ( x 1 , x 2 , ⋯ , x n ) X=(x_1,x_2,\cdots,x_n) X=(x1,x2,⋯,xn)是一个差分约束系统的一个解， d d d为任意常数，那么 X + d = ( x 1 + d , x 2 + d , ⋯ , x n + d ) X+d=(x_1+d,x_2+d,\cdots,x_n+d) X+d=(x1+d,x2+d,⋯,xn+d)也是该系统的解。
证明：对于每个 x i x_i xi和 x j x_j xj，有 ( x j + d ) − ( x i + d ) = x j − x i (x_j+d)-(x_i+d)=x_j-x_i (xj+d)−(xi+d)=xj−xi。因此，若 X X X是这个差分约束系统的一个解，那么 X + d X+d X+d也是这个系统的解
例如：
X = { x 1 − x 2 ≤ 0 x 1 − x 5 ≤ − 1 x 2 − x 5 ≤ 1 x 3 − x 1 ≤ 5 x 4 − x 1 ≤ 4 x 4 − x 3 ≤ − 1 x 5 − x 3 ≤ − 3 x 5 − x 4 ≤ − 3 X=\begin{cases} x_1-x_2\leq 0 \\ x_1-x_5\leq -1 \\ x_2-x_5\leq 1\\ x_3-x_1\leq 5\\ x_4-x_1\leq 4\\ x_4-x_3\leq -1\\ x_5-x_3\leq -3\\ x_5-x_4\leq -3\end{cases} X=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧x1−x2≤0x1−x5≤−1x2−x5≤1x3−x1≤5x4−x1≤4x4−x3≤−1x5−x3≤−3x5−x4≤−3
该问题的一个解为 X = ( − 5 , − 3 , 0 , − 1 , − 4 ) X=(-5,-3,0,-1,-4) X=(−5,−3,0,−1,−4)，令一个解为 X ′ = ( 0 , 2 , 5 , 4 , 1 ) X'=(0,2,5,4,1) X′=(0,2,5,4,1)，这两个解是有联系的， X ′ X' X′中的每个元素比 X X X中的相应元素大5
这也正说明了，如果 X X X是一个差分约束系统的解，那么 X + d X+d X+d也是这个系统的解
假设 ∀ i , X i ≤ c \forall i,X_i\leq c ∀i,Xi≤c，然后再增加一个超级源点0号节点，令 X 0 = 0 X_0=0 X0=0，令 d = − X 0 d=-X_0 d=−X0，等式两边同时加上 d d d，可得 X i − X 0 ≤ c − X 0 X_i-X_0\leq c-X_0 Xi−X0≤c−X0，即 X i − X 0 ≤ c X_i-X_0\leq c Xi−X0≤c。这样一来，就多了 N N N个形如 X i − X 0 ≤ 0 X_i-X_0\leq 0 Xi−X0≤0的约束条件，应该从节点0向每个节点 i i i连一条长度为0的有向边。
约束图
对于 n n n个变量， m m m个约束条件来说，其实就是对应于图论中的 n n n个节点， m m m条边。对于 i = 1 , 2 , ⋯ , n i=1,2,\cdots,n i=1,2,⋯,n，图中的每一个顶点 v i v_i vi对应着 n n n个未知量中的一个 x i x_i xi，图中的每个有向边对应着关于两个未知量的 m m m个不等式的其中一个。
对于一个差分约束系统来说，相应的约束图是一个带权有向图 G = ( V , E ) G=(V,E) G=(V,E)，其中 V = V= V={ v 0 , v 1 , ⋯ , v n v_0,v_1,\cdots,v_n v0,v1,⋯,vn}，而且 E = E= E={ ( v i , v j ) : x j − x i ≤ b k (v_i,v_j):x_j-x_i\leq b_k (vi,vj):xj−xi≤bk} ⋃ \bigcup ⋃ { ( v 0 , v 1 ) , ( v 0 , v 2 ) , ⋯ , ( v 0 , v n ) (v_0,v_1),(v_0,v_2),\cdots,(v_0,v_n) (v0,v1),(v0,v2),⋯,(v0,vn)}
这里引入超级源点 v 0 v_0 v0是为了保证其他每个顶点 v 1 , v 2 , ⋯ , v n v_1,v_2,\cdots,v_n v1,v2,⋯,vn均从 v 0 v_0 v0可达。因此，顶点集合 V V V由对应于每个未知量 x i x_i xi的顶点 v i v_i vi和附加的顶点 v 0 v_0 v0所组成。边的集合 E E E由对应于每个差分约束条件的边与对应于每个未知量 x i x_i xi的边 ( v 0 , v i ) (v_0,v_i) (v0,vi)所构成。如果 x j − x i ≤ b k x_j-x_i\leq b_k xj−xi≤bk是一个差分约束，则边 ( v i , v j ) (v_i,v_j) (vi,vj)的权 w ( v i , v j ) = b k w(v_i,v_j)=b_k w(vi,vj)=bk。从超级源点 v 0 v_0 v0出发的每条边的权值均为0。
约束图如下：
定理
给定一个差分约束系统，设 G = ( V , E ) G=(V,E) G=(V,E)为其相应的约束图。如果 G G G不包含负权回路(即负环)，那么
X = ( δ ( v 0 , v 1 ) , δ ( v 0 , v 2 ) , δ ( v 0 , v 3 ) , ⋯ , δ ( v 0 , v n ) ) X=(\delta (v_0,v_1),\delta (v_0,v_2),\delta (v_0,v_3),\cdots,\delta (v_0,v_n)) X=(δ(v0,v1),δ(v0,v2),δ(v0,v3),⋯,δ(v0,vn))
是此系统的一个可行解。当且仅当 G G G中存在负环时，该系统不存在可行解。
上式中 δ ( v 0 , v 1 ) \delta(v_0,v_1) δ(v0,v1)表示超级源点 v 0 v_0 v0到节点 v 1 v_1 v1的真实的最短距离，其他同理。跑一边最短路算法后得到的 d i s t [ v 1 ] dist[v_1] dist[v1]其实就是 δ ( v 0 , v 1 ) \delta(v_0,v_1) δ(v0,v1)
证明：
-
首先来证明，如果 G G G中不存在负环时，那么可以求出一个可行解。考察任意边 ( v i , v j ) ∈ E (v_i,v_j)\in E (vi,vj)∈E，由三角不等式 δ ( v 0 , v j ) ≤ δ ( v 0 , v i ) + w ( v i , v j ) \delta (v_0,v_j)\leq \delta (v_0,v_i)+w(v_i,v_j) δ(v0,vj)≤δ(v0,vi)+w(vi,vj)，即 δ ( v 0 , v j ) − δ ( v 0 , v i ) ≤ w ( v i , v j ) \delta (v_0,v_j)-\delta (v_0,v_i)\leq w(v_i,v_j) δ(v0,vj)−δ(v0,vi)≤w(vi,vj)。因此，设 x i = δ ( v 0 , v i ) , x j = δ ( v 0 , v j ) x_i=\delta (v_0,v_i),x_j=\delta(v_0,v_j) xi=δ(v0,vi),xj=δ(v0,vj)，带入上式子可知满足对应边 ( v i , v j ) (v_i,v_j) (vi,vj)的差分约束 x j − x i ≤ w ( v i , v j ) x_j-x_i\leq w(v_i,v_j) xj−xi≤w(vi,vj)
-
接下来再来证明，如果 G G G中存在负环，那么差分约束系统不存在可行解。设负权回路为 c = < v 1 , v 2 , ⋯ , v k > c=<v_1,v_2,\cdots,v_k> c=<v1,v2,⋯,vk>，其中 v 1 = v k v_1=v_k v1=vk（因为节点 v 0 v_0 v0没有入边，所以它不可能再回路 c c c上）。回路 c c c对应着如下的差分约束：
{ x 2 − x 1 ≤ w ( v 1 , v 2 ) x 3 − x 2 ≤ w ( v 2 , v 3 ) ⋯ x k − x k − 1 ≤ w ( v k − 1 , v k ) x 1 − x k ≤ w ( v k , v 1 ) \begin{cases}x_2-x_1\leq w(v_1,v_2)\\ x_3-x_2\leq w(v_2,v_3)\\ \cdots \\ x_k-x_{k-1}\leq w(v_{k-1},v_k)\\ x_1-x_k\leq w(v_k,v_1) \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧x2−x1≤w(v1,v2)x3−x2≤w(v2,v3)⋯xk−xk−1≤w(vk−1,vk)x1−xk≤w(vk,v1)
假设存在满足 k k k个不等式的一个解 X X X，那么也满足上述 k k k个不等式相加所得到的不等式。如果把这些不等式相加，就会发现每个变量 x i x_i xi的正负项相互抵消了，结果左边项和为0，而右边项和为 w ( c ) w(c) w(c)，因此有 0 ≤ w ( c ) 0\leq w(c) 0≤w(c)。但是由于 c c c是一个负权回路，因此有 w ( c ) < 0 w(c)<0 w(c)<0，因此得到矛盾 0 ≤ w ( c ) < 0 0\leq w(c)<0 0≤w(c)<0，由此得证
求不等式组的可行解：
源点需要满足的条件：从源点出发，一定可以走到所有边
步骤：
- 先将每个不等式 x i ≤ x j + c k x_i\leq x_j+c_k xi≤xj+ck，转化为一条从 x j x_j xj走到 x i x_i xi，长度为 c k c_k ck的一条边
- 找到一个超级源点，使得该源点一定可以遍历到所有边
- 从源点求一边单源最短路
- 如果存在负环，则原不等式组一定无解
- 如果不存在负环，则 X = ( d i s t [ v 1 ] , d i s t [ v 2 ] , ⋯ , d i s t [ v n ] ) X=(dist[v_1],dist[v_2],\cdots,dist[v_n]) X=(dist[v1],dist[v2],⋯,dist[vn])的一个可行解
在某些题目中，约束条件形如 X i − X j ≥ c k X_i-X_j\geq c_k Xi−Xj≥ck，我们仍然可以从 j j j到 i i i连一条长度为 c k c_k ck的有向边，只不过现在应该要计算单源最长路，若图中存在正环则无解。当然，我们也可以把约束条件转换为 X j − X i ≤ − c k X_j-X_i\leq -c_k Xj−Xi≤−ck，再按照单源最短路进行计算
最大值和最小值
对于给定的一组不等式关系，如何求出每个变量的最大值或者最小值呢？
什么是最大值或最小值？
这里的意思是说，比如你求出了一个解 X = ( x 1 , x 2 , ⋯ , x n ) X=(x_1,x_2,\cdots,x_n) X=(x1,x2,⋯,xn)，那么 X ′ = ( x 1 + d , x 2 + d , ⋯ , x n + d ) X'=(x_1+d,x_2+d,\cdots,x_n+d) X′=(x1+d,x2+d,⋯,xn+d)也是一个解， X ′ ′ = ( x 1 + 2 d , x 2 + 2 d , ⋯ , x 3 + 3 d ) X''=(x_1+2d,x_2+2d,\cdots,x_3+3d) X′′=(x1+2d,x2+2d,⋯,x3+3d)也是一个解，那么我想知道某个变量 x i x_i xi的最大值，那么到底是取 x i x_i xi还是 x i + d x_i+d xi+d还是 x i + 2 d x_i+2d xi+2d呢？同理，求某个变量 x i x_i xi的最小值也是一样的含义。
结论：
- 如果求的是最小值，那么应该求单源最长路
- 如果求的是最大值，那么应该求单源最短路
证明：
以求 x i x_i xi的最大值为例：
求所有从 x i x_i xi出发，构成的多个形如如下的不等式链：
x i ≤ x j + c m ≤ x k + c m + c n ≤ ⋯ ≤ x 0 + c 0 + c 4 + ⋯ + c n + c m x_i\leq x_j+c_m\leq x_k+c_m+c_n\leq \cdots \leq x_0+c_0+c_4+\cdots +c_n+c_m xi≤xj+cm≤xk+cm+cn≤⋯≤x0+c0+c4+⋯+cn+cm，其中 x 0 = 0 , c 0 = 0 x_0=0,c_0=0 x0=0,c0=0，令 F = F= F= x 0 + c 0 + c 4 + ⋯ + c n + c m x_0+c_0+c_4+\cdots +c_n+c_m x0+c0+c4+⋯+cn+cm
那么 x i x_i xi的最大值，要注意 F F F可能多很多个，因此，我们取 F F F中最小的那个值，就是 x i x_i xi的最大值
例如 x i ≤ 5 , x i ≤ 7 , x i ≤ 9 x_i\leq 5,x_i\leq 7,x_i\leq 9 xi≤5,xi≤7,xi≤9，那么 x i x_i xi的最大值为5。假设 x i x_i xi取最大值为9，那么就不满足 x i ≤ 5 x_i\leq 5 xi≤5和 x i ≤ 7 x_i\leq 7 xi≤7了。
把上述转换成图论的问题，其实就是求 d i s t [ i ] dist[i] dist[i]的最小值（因为 F F F表示的是从起点出发，到达某个点的距离。那么求 F F F的最小值，其实就是求单源最短路），那么就可以用最短路来求解。
以求 x i x_i xi的最小值为例：
求所有从 x i x_i xi出发，构成的多个形如如下的不等式链：
x i ≥ x j + c m ≥ x k + c m + c n ≥ ⋯ ≥ x 0 + c 0 + c 4 + ⋯ + c n + c m x_i\geq x_j+c_m\geq x_k+c_m+c_n\geq \cdots \geq x_0+c_0+c_4+\cdots +c_n+c_m xi≥xj+cm≥xk+cm+cn≥⋯≥x0+c0+c4+⋯+cn+cm，其中 x 0 = 0 , c 0 = 0 x_0=0,c_0=0 x0=0,c0=0，令 F = F= F= x 0 + c 0 + c 4 + ⋯ + c n + c m x_0+c_0+c_4+\cdots +c_n+c_m x0+c0+c4+⋯+cn+cm
那么 x i x_i xi的最小值，要注意 F F F可能多很多个，因此，我们取 F F F中最大的那个值，就是 x i x_i xi的最小值
例如 x i ≥ 5 , x i ≥ 7 , x i ≥ 9 x_i\geq 5,x_i\geq 7,x_i\geq 9 xi≥5,xi≥7,xi≥9，那么 x i x_i xi的最大值为9。假设 x i x_i xi取最小值为5，那么就不满足 x i ≥ 7 x_i\geq 7 xi≥7和 x i ≥ 9 x_i\geq 9 xi≥9了。
下面举个图例：
X = { x 2 − x 1 ≤ c 1 x 3 − x 2 ≤ c 2 x 3 − x 1 ≤ c 3 X=\begin{cases}x_2-x_1\leq c_1\\ x_3-x_2\leq c_2\\ x_3-x_1\leq c_3 \end{cases} X=⎩⎪⎨⎪⎧x2−x1≤c1x3−x2≤c2x3−x1≤c3
那么，我们可以求出这样的：
{ x 3 ≤ x 1 + c 3 x 3 ≤ x 1 + c 1 + c 2 \begin{cases}x_3\leq x_1+c_3\\ x_3\leq x_1+c_1+c_2 \end{cases} {x3≤x1+c3x3≤x1+c1+c2
可以看出，约束变量 x 3 x_3 x3的有两个条件，如果画到图中，就对应于有2条路径。那么当我们要求 x 3 x_3 x3的最大值时，取的肯定是 x 1 + c 3 x_1+c_3 x1+c3和 x 1 + c 1 + c 2 x_1+c_1+c_2 x1+c1+c2中的最小值，这样才能保证满足这两个约束条件，进而满足题目给定的所有原始的约束条件。
我们添加超级源点 s s s即 v 0 v_0 v0，那么有 x 1 − x 0 ≤ c 0 x_1-x_0\leq c_0 x1−x0≤c0，因此有如下：
{ x 3 ≤ x 0 + c 0 + c 3 x 3 ≤ x 0 + c 0 + c 1 + c 2 \begin{cases}x_3\leq x_0+c_0+c_3\\ x_3\leq x_0+c_0+c_1+c_2 \end{cases} {x3≤x0+c0+c3x3≤x0+c0+c1+c2
其中 x 0 = 0 , c 0 = 0 x_0=0,c_0=0 x0=0,c0=0
解释一样 x 0 + c 0 + c 3 x_0+c_0+c_3 x0+c0+c3的含义：它表示从源点 v 0 v_0 v0到达节点 v 3 v_3 v3所走过的路径上的权值之和。 x 0 + c 0 + c 1 + c 2 x_0+c_0+c_1+c_2 x0+c0+c1+c2也是一样的含义。
画图如下：
对应有两条路径：
- v 0 ⟹ v 1 ⟹ v 3 v_0\implies v_1\implies v_3 v0⟹v1⟹v3，从源点 v 0 v_0 v0走到节点 v 3 v_3 v3，所走过的路径之和为 c 0 + c 3 c_0+c_3 c0+c3
- v 0 ⟹ v 1 ⟹ v 2 ⟹ v 3 v_0\implies v_1\implies v_2\implies v_3 v0⟹v1⟹v2⟹v3，从源点 v 0 v_0 v0走到节点 v 3 v_3 v3，所走过的路径之和为 c 0 + c 1 + c 2 c_0+c_1+c_2 c0+c1+c2
- 可以发现，既然我们知道了等式右边的式子含义，其实就是求从源点出发到达某个节点的距离，由于可能存在多条路径，因此有多个值，那么我们只需要根据单源最短路径算法，就可以求出最小的那个值了，设为 F m i n F_{min} Fmin。因此，如果想要求某个变量 x i x_i xi的最大值，那么就要满足 M a x ( x i ) ≤ F m i n Max(x_i)\leq F_{min} Max(xi)≤Fmin。这也就是说，求变量 x i x_i xi的最大值，等价于跑一下单源最短路，求出最短路径的权值之和
因此，相应的就可以知道，要求 x i x_i xi的最小值，其实就是跑一下单源最长路，求出最长路径的权值之和。
总结
- x i ≥ x j + c x_i\geq x_j+c xi≥xj+c，则从节点 j j j向节点 i i i连一条长度为 c c c的边，要求变量 x i x_i xi的最小值，则跑一下最长路即可
- x i ≤ x j + c x_i\leq x_j+c xi≤xj+c，则从节点 j j j向节点 i i i连一条长度为 c c c的边，要求变量 x i x_i xi的最大值，则跑一下最短路即可
总结
- x i ≥ x j + c x_i\geq x_j+c xi≥xj+c，则从节点 j j j向节点 i i i连一条长度为 c c c的边，要求变量 x i x_i xi的最小值，则跑一下最长路即可
- x i ≤ x j + c x_i\leq x_j+c xi≤xj+c，则从节点 j j j向节点 i i i连一条长度为 c c c的边，要求变量 x i x_i xi的最大值，则跑一下最短路即可