差分约束『转』

第一：

感觉难点在于建图
第二：
①：对于差分不等式，a - b <= c ，建一条 b 到 a 的权值为 c 的边，求的是最短路，得到的是最大值
②：对于不等式 a - b >= c ，建一条 b 到 a 的权值为 c 的边，求的是最长路，得到的是最小值
③：存在负环的话是无解
④：求不出最短路（dist[ ]没有得到更新）的话是任意解
第三：
一种建图方法：
设x是第i位置（或时刻）的值（跟所求值的属性一样），那么把x看成数列，前n项和为s[n]，则x = s - s[i-1]；
那么这样就可以最起码建立起类似这样的一个关系：0 <= s - s[i-1] <= 1;
其他关系就要去题目探索了