最近学了差分约束系统，其实很早很早，可以追溯到半年前了，就知道什么是差分约束系统，就知道怎么解题了，不过当时还不会bellman-ford的算法，所以就搁浅了。然后这个学期学会了bellman-ford的算法，于是在一个睡不着的晚上用手机查资料，又回顾了一下，觉得自己想通了。可是...正所谓站着说话不腰疼，或者说通过实践才能真正的学会知识，前天做了差分约束的第一题，结果花了一晚上，真正真正的理解了差分约束！
这里插一句，本来打算今晚把1420也搞定后再写这个的，可是编译Linux那个内核弄的什么都很卡，风扇呼呼的，啥也做不下去，就写个记录吧~话说快2个小时了，不给力啊~！
至于概念已经解题什么的，不多说了，满天飞。说一个最重要的问题，至少是我认为最重要的问题：
我在弄清楚这一切前，总是不能想通大于小于的问题以及为什么求的是最长路？然而有的博客里又求的是最短路？...而且大多数博客和资料都没有详细谈这个问题（或许是我搜索资料的能力不强吧~~！）
最后明白了，思路整理如下：
差分约束的完整描述：满足一组不等式的一组变量，使得xn与x1的差值最小~
两个要求：一组不等式！ xn与x1的差值最小！
要求x2 - x1 >= c，那么说明，从x1到x2的路径长度必须大于c，于是我们就给x1到x2搭一条路，最后求从x1到xn的最长路（说明一下，个人感觉这是差分约束的核心内容，但是我理解了很长时间。最后我一边默念这句话一边想，终于想通了：因为x1到x2原来的路径是正无穷，当然也是满足条件的，但是我们现在求的是满足条件的xn-x1最小，就是说如果这条路c长度可以满足，我们就绝不搭长为c+1的路，所以我们搭了一条这样的路。）接下来，x3 - x1 >= d ; x2 - x3 >= e。这个时候，我们已经搭成这样:
3
/ \
d e
/ \
1 -- c --> 2
这时候如果d+e大于c的话，那么x1到x2的距离就必须更新为d+e了，为什么？因为原来的c不能满足条件了，虽然求最小，但是满足条件才是first！然后，其实，这时候表达式x1 - x2 >= c已经不管用了，x1 --- x3 --- x2 这条路径已经足够约束x1和x2啦！~
当然，反过来，求最短路也可以的，但是，需要倒着来。
结论，两个选择：
1. 如果 xi - xj >= w,那么从xj到xi连一条又向边，然后求从前往后（假设j < i）的最长路；
2. 如果 xi - xj >= w,那么转化为xj - xi <= -w，于是从xi到xj连一条有向边，然后求从后往前的最短路（亦假设j<i）。
其他问题就不说了，bellman-ford或者SPFA，搭完路就开始(n - 1)次松弛和一次检验，n为顶点数。
不过在实际应用中，一般不是真正的不等式组，不是给出一些二元不等式，而是这样：
给出一个序列，1至n这n个数字，然后已知从 i 到 j 的数字和至多a、至少b，给出这么一组，然后求每个数字最小为多少，或者求总和最小为多少。
于是构造，设s[i]为0到i的和，那么s[1]即为第一个数字，s[2]-s[1]即为第二个数字，于是给出的条件转换为：
s[i] - s[j] >= b
s[i] - s[j] <= a
s[i] - s[i-1] >= 0
s[i] - s[i-1] <= V （*如果是1到n这n个容器，每个容器有容量，或者特殊情况n个布尔值，那么需要加上这个限制条件）
具体例子在这里 hit
这里插一句，本来打算今晚把1420也搞定后再写这个的，可是编译Linux那个内核弄的什么都很卡，风扇呼呼的，啥也做不下去，就写个记录吧~话说快2个小时了，不给力啊~！
至于概念已经解题什么的，不多说了，满天飞。说一个最重要的问题，至少是我认为最重要的问题：
我在弄清楚这一切前，总是不能想通大于小于的问题以及为什么求的是最长路？然而有的博客里又求的是最短路？...而且大多数博客和资料都没有详细谈这个问题（或许是我搜索资料的能力不强吧~~！）
最后明白了，思路整理如下：
差分约束的完整描述：满足一组不等式的一组变量，使得xn与x1的差值最小~
两个要求：一组不等式！ xn与x1的差值最小！
要求x2 - x1 >= c，那么说明，从x1到x2的路径长度必须大于c，于是我们就给x1到x2搭一条路，最后求从x1到xn的最长路（说明一下，个人感觉这是差分约束的核心内容，但是我理解了很长时间。最后我一边默念这句话一边想，终于想通了：因为x1到x2原来的路径是正无穷，当然也是满足条件的，但是我们现在求的是满足条件的xn-x1最小，就是说如果这条路c长度可以满足，我们就绝不搭长为c+1的路，所以我们搭了一条这样的路。）接下来，x3 - x1 >= d ; x2 - x3 >= e。这个时候，我们已经搭成这样:
3
/ \
d e
/ \
1 -- c --> 2
这时候如果d+e大于c的话，那么x1到x2的距离就必须更新为d+e了，为什么？因为原来的c不能满足条件了，虽然求最小，但是满足条件才是first！然后，其实，这时候表达式x1 - x2 >= c已经不管用了，x1 --- x3 --- x2 这条路径已经足够约束x1和x2啦！~
当然，反过来，求最短路也可以的，但是，需要倒着来。
结论，两个选择：
1. 如果 xi - xj >= w,那么从xj到xi连一条又向边，然后求从前往后（假设j < i）的最长路；
2. 如果 xi - xj >= w,那么转化为xj - xi <= -w，于是从xi到xj连一条有向边，然后求从后往前的最短路（亦假设j<i）。
其他问题就不说了，bellman-ford或者SPFA，搭完路就开始(n - 1)次松弛和一次检验，n为顶点数。
不过在实际应用中，一般不是真正的不等式组，不是给出一些二元不等式，而是这样：
给出一个序列，1至n这n个数字，然后已知从 i 到 j 的数字和至多a、至少b，给出这么一组，然后求每个数字最小为多少，或者求总和最小为多少。
于是构造，设s[i]为0到i的和，那么s[1]即为第一个数字，s[2]-s[1]即为第二个数字，于是给出的条件转换为：
s[i] - s[j] >= b
s[i] - s[j] <= a
s[i] - s[i-1] >= 0
s[i] - s[i-1] <= V （*如果是1到n这n个容器，每个容器有容量，或者特殊情况n个布尔值，那么需要加上这个限制条件）
具体例子在这里 hit
RSS Feed