【图论】差分约束系统

差分约束问题：

给定n个变量｛x0，x1，x2，……xn-1｝和m个形如xi-xj<=ai（xi-xj>=ai）的不等式，求xn-1-x0的最大（小）值。

例如n=4，m=5，不等式如图，求x3-x0的最大值。

考虑初中数学方法，我们可以通过不等式相加得到一些形如x3-x0<=bi的不等式，易得min｛bi｝即为所求最大值。

于是暴力手算得到以下三个不等式：

1.由（5）+（4）+（1）得到x3-x0<=7。

2.由（5）+（2）得到x3-x0<=9。

3.由（3）得到x3-x0<=8。

联立解得x3-x0<=7，最大值为7。

我不知道是否有人认为手算十分简便，不过我现在写起来感觉十分恶心。

于是我们考虑如何系统解决这类问题。

考虑另一个问题，给定一张有四个点，五条边的有向图，如图所示，

?

（图源网络，侵删我这辈子都不想画图了）

求第0个点到第3个点的最短路。

显然答案是7，根本不用进行什么演算。

那么这两个问题间有什么关联呢？

考虑我们将第一个问题中一些不等式的和转化为xn-1-x0<=bi的过程，

若只转换成一个不等式，即由xn-1-xi<=ai，xi-xj<=aj，xj-xk<=ak，……，xk-x0<=a0

求和可得xn-1-x0<=Σai。

那么这样的一个过程是否等价于，

在图上沿x0->xk（花费a0），……，xk->xj（花费ak），xj->xi（花费aj），xi->xn-1（花费ai）这些边走出的一条x0到xn-1，花费Σai的路径？

显然的，若使xn-1的值最大，则所有不等式都应当尽量取等，所以两者等价。

那么我们推广转换成K个不等式的情况，即有xk-x0<=b0，xk-x0<=b1，……，xk-x0<=bK这些不等式。

此时可以发现max｛xk-x0｝=min｛bi｝，即图上从x0到xn-1的最短路径的长度。

正确性得证。现在我们只需要打一个最短路板子就可以解决这个手算量MAX的差分约束问题了。

一般地，差分约束问题总可以转化为最短（长）路问题求解，

将每个形如xi-xj<=ai（xi-xj>=ai）的不等式转化成图上j->i，权值为ai的边，

以0为起点进行单原最短（长）路算法求解即可，答案为dis（n-1）。

（以最短路为例）最终图中必定满足对于任意i，j，

如果有j->i，权值ai的边存在，则dis（i）<=dis（j）+ai，严格满足差分约束。

反之，如果0->n-1的路径中存在负环或者0和n-1不连通，即不存在dis（n-1），则原问题无解。

在不等式上的表现即为xn-1-x0<=b中的b无限小，此时xn-1-x0的最大值不存在。

?

在算法竞赛中，差分约束系统的不等式约束关系一般是不明显的，需要我们自己抽象出模型进行解答。

（例题回头更。。洗洗睡了弃坑）