差分約束(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 過挺險的~