前言
差分约束系统应该是一个比较有用的算法。它建立在图的思想上，常与最短（长）路算法一起出现。
一道例题
下面是一组不等式：
[A-B≥5 ag{①}
]
[B-E≥7 ag{②}
]
[A-E≥6 ag{③}
]
[D-A≥9 ag{④}
]
[B-C≥6 ag{⑤}
]
[C-E≥2 ag{⑥}
]
现在问你一个问题：(A-E)的最小值是多少？
其实在这组不等式中，我们有很多方法得到一个形如(A-E≥x)的式子：
-
第一种方法：由③式直接得(A-E≥6)
-
第二种方法：①+②得(A-E≥12)
-
第三种方法：①+⑤+⑥得(A-E≥13)
因此，我们可以求出答案：(A-E)的最小值是13。
用差分约束系统来求解上面这个问题
通过我们刚才的解题步骤，我们可以总结归纳出一个解决该类问题的通用方法，也就是差分约束系统。
我们刚才通过(A-B≥5)、(B-C≥6)、(C-E≥2)来求出了(A-E≥13)，仔细观察可以发现，相邻的两个式子中都有一个相同的字母，而我们正是借助了这个字母来实现转移的。
是不是有一种熟悉的感觉？
这不就是最长路径嘛！
没错，对于一个类似于(A-B≥x)的式子，我们可以从(B)向(A)连一条有向边，且这条边的边权为(x)。
这样，对于上面这个问题，我们只需求出(E)至(A)的最长路即可。
不等式的转换
对于(A-B≥x)的式子，我们是从(B)向(A)连边求最长路，而对于(A-B≤x)，则需从(A)向(B)连边求最短路。
有一个要注意的地方，就是一张图你的式子要么全是(A-B≥x)的形式，要么全是(A-B≤x)的形式，不然你就无法用差分约束系统来求解答案了。
那么如果题目中给出多种式子呢？就不能用差分约束系统了吗？
不然，其实我们可以将这些式子全部转化为同一种式子（(A-B≥x)或(A-B≤x)，下面以(A-B≥x)为例）：
- (A=B)：这个式子可以拆成(A≥B)和(B≥A)，再转换一下就变成了(A-B≥0)和(B-A≥0)
- (A≤B)：这个式子可以转换成(B-A≥0)
- (A≥B)：这个式子可以转换成(A-B≥0)
- (A<B)：这个式子可以改写成(A≤B-1)，再转换一下就变成了(B-A≥1)
- (A>B)：这个式子可以改写成(A-1≥B)，再转换一下就变成了(A-B≥1)
- (A-B≤x)：这个式子可以转换成(B-A≥-x)
- (A-B≥x)：这个式子不用转换
- (A-B<x)：这个式子可以改写成(B-A>-x)，再转换一下就变成了(B-A≥1-x)
- (A-B>x)：这个式子可以转换成(A-B≥x+1)
这样，遇到给你一些不等式，请你求出两数之差的最大（最小）值的问题，就可以轻松解决了。