差分约束系统

差分约束系统

①求满足所有不等式的前提下，第i个不等式可取到的最大值（即max Xi - Xj [其中Xi,Xj是第i个不等式的Xi,Xj]）， 添加源点，将不等式转换成图【Xi - Xj <= c，化成边Vj -> Vi，权值为c】，求图的最短路径，对应的d[i]即为xi的最大值

①求满足所有不等式的前提下，第i个不等式可取到的最小值（即min Xi - Xj [其中Xi,Xj是第i个不等式的Xi,Xj]）， 添加源点，将不等式转换成图【Xi - Xj >= c，化成边Vj -> Vi，权值为c】，求图的最长路径，对应的d[i]即为xi的最小值

③判断不等式组是否有解，添加源点，将不等式转换成图，对图进行bellman-ford算法，判断有无负权环，有则无解，无则有解

X1 - X2 <= 0
X1 - X5 <= -1
X2 - X5 <= 1
X3 - X1 <= 5
X4 - X1 <= 4
X4 - X3 <= -1
X5 - X3 <= -3
X5 - X4 <= -3
不等式组(1) 

 这个不等式组要么无解，要么就有无数组解。因为如果有一组解{X1, X2, ..., Xn}的话，那么对于任何一个常数k，{X1 + k, X2 + k, ..., Xn + k}肯定也是一组解，因为任何两个数同时加一个数之后，它们的差是不变的，那么这个差分约束系统中的所有不等式都不会被破坏。  

差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。即对于任何一条边u -> v，都有：d(v) <= d(u) + w(u, v) 

显然以上不等式就是d(v) - d(u) <= w(u, v)。这个形式正好和差分约束系统中的不等式形式相同。于是我们就可以把一个差分约束系统转化成一张图，每个未知数Xi对应图中的一个顶点Vi，把所有不等式都化成图中的一条边。对于不等式Xi - Xj <= c，把它化成三角形不等式：Xi <= Xj + c，就可以化成边Vj -> Vi，权值为c。最后，我们在这张图上求一次单源最短路径，这些三角形不等式就会全部都满足了，因为它是最短路径问题的基本性质嘛。

 话说回来，所谓单源最短路径，当然要有一个源点，然后再求这个源点到其他所有点的最短路径。那么源点在哪呢？我们不妨自已造一个。以上面的不等式组为例，我们就再新加一个未知数X0。然后对原来的每个未知数都对X0随便加一个不等式（这个不等式当然也要和其它不等式形式相同，即两个未知数的差小于等于某个常数）。我们索性就全都写成Xn - X0 <= 0，于是这个差分约束系统中就多出了下列不等式： 

X1 - X0 <= 0
X2 - X0 <= 0
X3 - X0 <= 0
X4 - X0 <= 0
X5 - X0 <= 0
不等式组(2) 

 图中的每一条边都代表差分约束系统中的一个不等式。现在以V0为源点，求单源最短路径。最终得到的V0到Vn的最短路径长度就是Xn的一个解啦。从图1中可以看到，这组解是{0，-5, -3, 0, -1, -4}。其中0是源点到源点的最短路径，固定为0.

有一个有趣的性质，那就是通过最短路径算法求出来的一组解当中，所有未知数都达到最大值。

 

 

那么如果在一个未知数定死的情况下，要求其它所有未知数的最小值怎么办？只要反过来求最长路径就可以了。最长路径中的三角不等式与最短路径中相反：

d(v) >= d(u) + w(u, v)
也就是d(v) - d(u) >= w(u, v) 
    所以建图的时候要先把所有不等式化成大于等于号的。其它各种过程，包括证明为什么解出的是最小值的证法，都完全类似。

将不等式全部化成xi – xj >= k的形式，这样建立j->i的边，权值为k的边，如果不等式组中有xi – xj > k，因为一般题目都是对整形变量的约束，化为xi – xj >= k+1即可，如果xi – xj = k呢，那么可以变为如下两个：xi – xj >= k, xi – xj <= k,进一步变为xj – xi >= -k，建立两条边即可。

 

判断不等式组是否有解

如果要判断差分约束系统是否存在解，一般都是判断环，选择求最短路或者最长路求解都行，只是不等式标准化时候不同，判环地话，用Bellman-Ford即可，n个点中如果同一个点入队超过n次，那么即存在环。

如果存在负权环，则无解，反之有解。