差分约束(difference constraints)，对，两个关键字要理解好，“difference”简单理解就是两个节点的“差”，对应的就是图中的边权，而“约束”对应的是图的边。这个图的边权不一定都是正数，之前我一直很奇怪为什么做最短路的时候初始化dis[]为了0也可以，那是因为我没意识到边权可以为负数，而思维定势地想初始化dis[]为0，那0不就是最小路径了吗，但这里差分约束的最短路径常常是负数的，所以最短路径可以不是0！！
看网上讲解的时候要小心，很多人把最长路和最短路是不分的，乱死了。
还有很重要的一点很多人没区分开，
求最小可行解 ==> 把不等式划为dv >= dx + Z的形式，即建立<u,v,Z>边 ==> 可行解要最小，其实就是取约束条件中`最大`的约束 ==> 求最长路
解释：为什么求最小可行解要划成dv >= dx + Z形式？因为这个形式暗指了“让dv尽量小”，因为此刻dv的取值区间为[du+Z, ∞]。
为什么可行解最小，即意味着取最大约束条件？这样想，如果有dv >= du + Z1, dv >= du + Z2，(Z1<Z2)，那dv的最小取值就是du+Z2，因为du+Z1不满足第二个约束条件。
最后一步就好理解了，因为建图的边权就是约束值，既然上一步指要取最大约束，那当然是求最长路啦。
网上很多讲解没有区分开所谓的最大/最小，一会儿指可行解的最，一会儿指约束条件的最，弄得我乱了好久。
顺便贴一下：
求最大可行解 ==> 把不等式划为dv <= dx + Z的形式，即建立<u,v,Z>边 ==> 其实就是取约束条件中`最小`约束 ==> 求最短路
关于源点：很多时候额外价格源点可以帮我们把一个非连通图变成连通图，而对于源点的不等式，一定要和你之前建边时的不等式形式一样，如果之前是dv >= du + Z，那源点也要dv >= d0 + xxx。这个xxx就是dis[]的初始值，关于如何选取xxx，下面两句话摘自百度百科：
“
1.如果将源点到各点的距离初始化为0，最终求出的最短路满足 它们之间相互最接近了
2.如果将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最大。
”
差分约束题目我一般是用SPFA+栈，为什么不用dijkstra+heap？因为dijkstra不能处理负环，而我们的题目可能有负环，所以干脆都用SPFA了，多数条件下，用stack的SPFA比用queue的快，why？因为常常地，用最先更新了的点去更新其它点，效果比用以前已经更新了的点(在queue的tail)好。
差分约束专题：http://972169909-qq-com.iteye.com/blog/1185527
poj 1201 差分约束
题意：求符合题意的最小集合Z的元素个数，约束条件:i j C，表区间[i,j]至少有C个Z集合的元素。
隐含条件是，S区间是个连续的数字区间，0 <= s[i+1] - s[i] <= 1，其中s[i]表0~i中有多少数字是Z集合元素。下面是隐含条件的建边。
for(int i = 0; i < 50001; i++) { //@
vert[i].push_back(i+1); edge[i].push_back(0);
vert[i+1].push_back(i); edge[i+1].push_back(-1);
}
poj 1364 差分约束
题意：约束条件：i, n, op, K --> op分greater和less，需要满足Si + S[i+1] + S[i+2] + ... + S[i+n] > K （或小于）
因为我是用dis[i]表示S0+S1+...+Si的和，所以<u,v,w>应该表示的意思是sum[v]-sum[u-1] = w，所以这里0也是一个点，所以源点不能取0！
//@ ?? 我在SPFA后面输出了dis[]数组来看，这些值并不符合题目的要求，那为什么整个程序是对的？如果要输出一个解的话怎么写？
答：因为这里的dis[i]表示的是s1+s2+...+si的和，用第一个样例来说，
sample input:
4 2
1 2 gt 0
2 2 lt 2
输出的dis[0--n] : -1 0 0 0 0
s1+s2+s3 = sum[3] - sum[1-1] = dis[3] - dis[0] = 1 , 满足gt 0
s2+s3+s4 = sum[4] - sum[2-1] = dis[4] - dis[1] = 0 , 满足lt 2
所以，{si}的一组解应该为0,1,0,0,0.
poj 1983 差分约束
题意：给出两种约束条件，一种是P A B X，意为精确地约束A比B远X个单位；另一种V A B，意为模糊地约束A至少比B远1个单位。是否有可行解？
好点：两种约束条件，其中Precise约束可以转换为X <= A-B <= X
有V i i 这种数据，这种数据在SPFA里会WA，在ballman_ford里AC，不过预处理一下就可以了，还是用SPFA.
hdu 3666 差分约束
题意：给出矩阵{Cij}，问是否存在数列{A} 和 {B}，使得对于矩阵内所有Xij满足: L <= Xij * Ai / Bj <= U
构图。用log把乘除变成加减，就可以差分约束来做了。我用的是SPFA+stack求最短路，最长路应该也是可以的。没有建源点，直接一开>始把所有点push进去... 14xx ms 过挺险的~