差分约束原理及其应用

经典应用：求不等式组的解

差分约束系统是一组n元一次不等式组，描述了n个变量x1~xn  之间的m对相对关系，其中每一个变量都可以变成形如xi-xj<=ck,再来可以进一步变形成xi<=xj+ck,这一条式子和求最短路算法里面的三角不等式dist[y]<=dist[x]+ z及其相似，因此可以尝试将不等式往求最短路上面靠。

对于每一个形如xi<=xj+ck的式子都可以将其转换成图上的一条由点xj指向xi的边权为ck的有向边。

到此，就可以将你不等式问题转化成求一个最短路问题。

（1）求不等式组的可行解

前提条件：为了求出一组可行解首先是要将所有的点都联通起来，为了在求源点到每一个点的最短路的时候可以遍历到每一个节点，因此选择源点的时候要选择一个可以走到每一个点的节点。

原不等式组无解的情况：    在图上存在负环

证明：如下图一组三元不等式组所示

又或者在约束条件变成形如xi-xj>=ck时 . 还是可以将其变成 xi>=xj+ck,仍然从xj到xi连一条长度为ck的边，只不过只一次变成了求最长路，并且无解的判断条件变成了是否存在正环，其余的方面都和求最短的时候类似。

（2）如何求不等式组的最大值或者说最小值：

结论：如果求的是最小值，应该求最长路，如果过求的是最大值，应该用求最短路

在一般的问题当中通常会有某一个点会给出一个具体的常量关系，形如xi<=c.

对此，通常都是建立一个超级源点0，使得0 -> xi, 边的长度为c。

如果没有上面的这个式子的话，就无法求出一组确切的可行解。因为不等式组给的是一组相对的关系，是可以进行放缩的，比如如果过{x1,x2,x3,x4}是一组可行解，{x1+d,x2+d,x3+d,x4+d}也是一组可行解，其中d是任意常数。

以求xi的最大值为例：

xi的最大值就是从0点出发到达xi的所有最短路径中最小值

证：因为在图里面可能会有多条不同的路径可以到达点xi，转化成不等式关系如下一个简单例子

图中的每一条路径都对应着不等式组可以转化得到的一条不等式链，dist[xi]的值在要满足每一条式子的同时保证值最大就是要在所有的上界里面求出上界最小的一个，那个就是xi的最大值。

又或者说，你问我条件变成xi>=c的时候怎么求最大值，这种情况下时没有最大值的，只有最小值。求最小值的话就是在所有的下界里面选择最大的一个式子

xi>=2

xi>=5

xi>=7

xi的最小值就是7.