差分約束(difference constraints)，對(duì)，兩個(gè)關(guān)鍵字要理解好，“difference”簡(jiǎn)單理解就是兩個(gè)節(jié)點(diǎn)的“差”，對(duì)應(yīng)的就是圖中的邊權(quán)，而“約束”對(duì)應(yīng)的是圖的邊。這個(gè)圖的邊權(quán)不一定都是正數(shù)，之前我一直很奇怪為什么做最短路的時(shí)候初始化dis[]為了0也可以，那是因?yàn)槲覜]意識(shí)到邊權(quán)可以為負(fù)數(shù)，而思維定勢(shì)地想初始化dis[]為0，那0不就是最小路徑了嗎，但這里差分約束的最短路徑常常是負(fù)數(shù)的，所以最短路徑可以不是0！！
看網(wǎng)上講解的時(shí)候要小心，很多人把最長(zhǎng)路和最短路是不分的，亂死了。
還有很重要的一點(diǎn)很多人沒區(qū)分開，
求最小可行解 ==> 把不等式劃為dv >= dx + Z的形式，即建立<u,v,Z>邊 ==> 可行解要最小，其實(shí)就是取約束條件中`最大`的約束 ==> 求最長(zhǎng)路
解釋：為什么求最小可行解要?jiǎng)澇蒬v >= dx + Z形式？因?yàn)檫@個(gè)形式暗指了“讓dv盡量小”，因?yàn)榇丝蘢v的取值區(qū)間為[du+Z, ∞]。
為什么可行解最小，即意味著取最大約束條件？這樣想，如果有dv >= du + Z1, dv >= du + Z2，(Z1<Z2)，那dv的最小取值就是du+Z2，因?yàn)閐u+Z1不滿足第二個(gè)約束條件。
最后一步就好理解了，因?yàn)榻▓D的邊權(quán)就是約束值，既然上一步指要取最大約束，那當(dāng)然是求最長(zhǎng)路啦。
網(wǎng)上很多講解沒有區(qū)分開所謂的最大/最小，一會(huì)兒指可行解的最，一會(huì)兒指約束條件的最，弄得我亂了好久。
順便貼一下：
求最大可行解 ==> 把不等式劃為dv <= dx + Z的形式，即建立<u,v,Z>邊 ==> 其實(shí)就是取約束條件中`最小`約束 ==> 求最短路
關(guān)于源點(diǎn)：很多時(shí)候額外價(jià)格源點(diǎn)可以幫我們把一個(gè)非連通圖變成連通圖，而對(duì)于源點(diǎn)的不等式，一定要和你之前建邊時(shí)的不等式形式一樣，如果之前是dv >= du + Z，那源點(diǎn)也要dv >= d0 + xxx。這個(gè)xxx就是dis[]的初始值，關(guān)于如何選取xxx，下面兩句話摘自百度百科：
“
1.如果將源點(diǎn)到各點(diǎn)的距離初始化為0，最終求出的最短路滿足 它們之間相互最接近了
2.如果將源點(diǎn)到各點(diǎn)的距離初始化為INF(無窮大)，其中之1為0，最終求出的最短路滿足 它們與該點(diǎn)之間相互差值最大。
”
差分約束題目我一般是用SPFA+棧，為什么不用dijkstra+heap？因?yàn)閐ijkstra不能處理負(fù)環(huán)，而我們的題目可能有負(fù)環(huán)，所以干脆都用SPFA了，多數(shù)條件下，用stack的SPFA比用queue的快，why？因?yàn)槌３５兀米钕雀铝说狞c(diǎn)去更新其它點(diǎn)，效果比用以前已經(jīng)更新了的點(diǎn)(在queue的tail)好。
差分約束專題：http://972169909-qq-com.iteye.com/blog/1185527
poj 1201 差分約束
題意：求符合題意的最小集合Z的元素個(gè)數(shù)，約束條件:i j C，表區(qū)間[i,j]至少有C個(gè)Z集合的元素。
隱含條件是，S區(qū)間是個(gè)連續(xù)的數(shù)字區(qū)間，0 <= s[i+1] - s[i] <= 1，其中s[i]表0~i中有多少數(shù)字是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 （或小于）
因?yàn)槲沂怯胐is[i]表示S0+S1+...+Si的和，所以<u,v,w>應(yīng)該表示的意思是sum[v]-sum[u-1] = w，所以這里0也是一個(gè)點(diǎn)，所以源點(diǎn)不能取0！
//@ ?? 我在SPFA后面輸出了dis[]數(shù)組來看，這些值并不符合題目的要求，那為什么整個(gè)程序是對(duì)的？如果要輸出一個(gè)解的話怎么寫？
答：因?yàn)檫@里的dis[i]表示的是s1+s2+...+si的和，用第一個(gè)樣例來說，
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}的一組解應(yīng)該為0,1,0,0,0.
poj 1983 差分約束
題意：給出兩種約束條件，一種是P A B X，意為精確地約束A比B遠(yuǎn)X個(gè)單位；另一種V A B，意為模糊地約束A至少比B遠(yuǎn)1個(gè)單位。是否有可行解？
好點(diǎn)：兩種約束條件，其中Precise約束可以轉(zhuǎn)換為X <= A-B <= X
有V i i 這種數(shù)據(jù)，這種數(shù)據(jù)在SPFA里會(huì)WA，在ballman_ford里AC，不過預(yù)處理一下就可以了，還是用SPFA.
hdu 3666 差分約束
題意：給出矩陣{Cij}，問是否存在數(shù)列{A} 和 {B}，使得對(duì)于矩陣內(nèi)所有Xij滿足: L <= Xij * Ai / Bj <= U
構(gòu)圖。用log把乘除變成加減，就可以差分約束來做了。我用的是SPFA+stack求最短路，最長(zhǎng)路應(yīng)該也是可以的。沒有建源點(diǎn)，直接一開>始把所有點(diǎn)push進(jìn)去... 14xx ms 過挺險(xiǎn)的~