这篇文章上次修改于 243 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
ACM程序课算法笔记11——差分约束
差分约束方程组
差分约束指的是一种多个元素之间差的限制，而求某两个值的最大差。
例如求：
x1 - x0 <= 2——①
x2 - x0 <= 7——②
x3 - x0 <= 8——③
x2 - x1 <= 3——④
x3 - x2 <= 2——⑤
求x3-x0的最大值。
对于这个式子，我们可以通过很简单的联立来获得关系式
x3 - x0 <= 8——③
(x3 - x2) + (x2 - x0) <= 7 + 2——②⑤
(x3 - x2) + (x2 - x1) + (x1 - x0) <= 2 + 3 + 2——①④⑤
最终三式子得到 8 9 7三个值
得到x3 - x0 <= 7
问题转化一（<= & <）
通过上式的联立我们可以很快发现，这三个值的获取，就相当于从x0直接走到x3，从x0走过x2再到x3等等。这和有向图是几乎一样的。
无异于 0->1 边权2，0->2 边权7，0->3 边权8，1->2 边权3，2->3 边权2
当我要求x3的最大值时，也就是求0到3的最短路径。
注意为什么是最短路径，当你求的是最大值的时候，你得到的路径权值是约束条件，如同上面的8 9 7一样，是小于等于它们，所以我们要取最小的，也就是最短路径。
问题转化二（>= & >）
上面是最好理解的<=符号，现在当遇到>=时，也就两边取负变号，也就变成了上面一样的方式，只不过边权取负，方向相反。
或者是换一个理解方式，所有都为>=，此时就需要转换一下，所有的值都变成大于等于，最后联立得到的多个约束值也是大于等于，此时就是找到多个约束值的最大值，最后求的也是最小值。就变成了最大路径问题。
注意：Dij不能用于计算最大路径问题，原因是贪心思路的时候，dij的最短路保证最短路径的那个点已经是答案了，但对于最长路，最长路径的点也不一定是答案，破坏了贪心的思路。
问题转化三（=）
当遇到=的要求时，实际上就是两个符号的组合起来，=等价于>=&<=，同时满足两个条件，这也就是一个双向的边，不过要注意权值正负不同。
例题：整数区间
内容：
给定 n 个整数闭区间 [ai, bi] 和 n 个整数 c1, …, cn。
读取区间数、它们的端点和整数 c1, …, cn，
计算整数集 Z 的最小大小，该数集满足和区间 [ai , bi]至少有 ci 个公共元素( i = 1, 2, …, n )
题解：
这是一道很隐藏的差分约束，其特点难以发现。我们不妨记录a[i]代表前i个数字，区间选择了a[i]个数，那么对于区间[left, right]内至少要选择c个元素也就是
a[right] - a[left - 1] >= c
同时我们还有个差分条件也就是
1 >= a[x] - a[x - 1] >= 0
根据以上约束条件做出边即可
又水了一篇博客
