什么是差分约束系统？
差分约束系统是一种特殊的N元一次不等式组。它包含N个变量X1 ~ XN, M个约束条件，形如Xi - Xj <= ck(常数)。
解决的问题是求出一组满足不等式组的可行解。
怎么求？
通过观察不等式可以发现每个不等式都可以变成Xi <= Xj + ck, 或者变成 Xj >= Xi - ck的形式， 很明显这两个三角不等式分别与求最短路和最长路的更新条件类似。
下面以求最短路为例。
因此我们可以把所有的变量当成一个点，所有约束条件当成一条边来建立无向图，比如Xi <= Xj + ck 可以建立一条
从Xj 到 Xi 长度为ck的一条边，然后做一遍最短路算法。
但是我们要找到一个源点：满足该点必须能到达任意一个点，因为如果到不了其中的某一个点的话，那么 这个点就不会被更新也就不知道满不满足不等式的条件。
假设源点是S，只需要建立N条从S到 Xi的无向边，那么就等价 Xi <= S + c0, 假如题目中没有对任何一个Xi 有常量限制，
比如Xi >= c 那么该题只能求解出来任意一个Xi的相对可行解， 而不能求出绝对的可行解。假如题目限制Xi <= c, 那么
上面的c0 = c， S = 0即可。
题目出现无解的情况就是存在Xi < Xi ，怎么对应到图中呢?

得出结论存在无解就是存在负环。
同理对于建立求解最长路的图中无解就是存在正环。
如何求解最大值或者最小值呢？
结论1 求解最大值就是求一遍最短路。
结论2 求解最小值就是求一遍最长路。
结论一正确性？
首先要求最大值肯定会有一个常量约束条件 Xi <= c;因为没有给出明确的上限是无法求出最大值的。
求最大值我们用到的约数条件一定Xi <= Xj + ck 只有满足每个变量有上限才有可能存在最大值。
对于每一个Xi 可能存在多条链形如 Xi <= Xj + ck <= Xj1 + ck1 + ck <= … <= S + ckn + ckn - 1 + … + ck;
以为Xi要满足所以像这样的链，如果Xi要满足所以条件，Xi必须 <= 所以链的最小值，因此就是求一遍最短路 的过程。
同理结论二恰好相反， 等价于求一遍最长路的过程。