圖論差分約束系統(tǒng)詳解

1、差分約束系統(tǒng)在一個差分約束系統(tǒng)(system of difference constras)中，線性規(guī)劃矩陣 A 的每一行包含一個 1 和一個-1，A 的其他所有元素都為 0。因此，由 Axb 給出的約束條件是 m 個差分約束集合，其中包含 n 個未知量，對應的線性規(guī)劃矩陣 A 為 m 行n 列。每個約束條件為如下形式的簡單線性不等式：xj-xibk。其中 1i,jn，1km。例如，考慮這樣一個問題，尋找一個 5 維向量x=(xi)以滿足：這一問題等價于找出未知量 xi，i=1,2,5，滿足下列 8 個差分約束條件：x1-x20 x1-x5-1x2-x51x3-x15x4-x14x4-x3-1

2、x5-x3-3x5-x4-3該問題的一個解為 x=(-5,-3,0,-1,-4)，另一個解 y=(0,2,5,4,1)，這 2 個解是有聯(lián)系的：y 中的每個元素比x 中相應的元素大 5。引理：設(shè) x=(x1,x2,xn)是差分約束系統(tǒng) Axb 的一個解，d 為任意常數(shù)。則x+d=(x1+d,x2+d,xn+d)也是該系統(tǒng) Axb 的一個解。約束圖在一個差分約束系統(tǒng) Axb 中，m X n 的線性規(guī)劃矩陣A 可被看做是n 頂點，m 條邊的圖的關(guān)聯(lián)矩陣。對于 i=1,2,n，圖中的每一個頂點 vi 對應著n 個未知量的一個 xi。圖中的每個有向邊對應著關(guān)于兩個未知量的 m 個不等式中的一個。給定一

3、個差分約束系統(tǒng) Axb，相應的約束圖是一個帶權(quán)有向圖 G=(V,E)，其中V=v0,v1,vn，而且 E= (vi,vj) : xj-xibk 是一個約束 (v0,v1) , (v0,v2) , ,(v0,vn) 。引入附加頂點 v0 是為了保證其他每個頂點均從 v0 可達。因此，頂點集合 V 由對應于每個未知量 xi 的頂點vi 和附加的頂點 v0 組成。邊的集合E 由對應于每個差分約束條件的邊與對應于每個未知量 xi 的邊(v0,vi)。如果 xj-xibk 是一個差分約束，則邊(vi,vj)的權(quán) w(vi,vj)=bk（注意 i 和 j 不能顛倒），從 v0 出發(fā)的每條邊的權(quán)值均為 0。

4、定理：給定一差分約束系統(tǒng) Axb，設(shè) G=(V,E)為其相應的約束圖。如果 G 不包含負權(quán)回路，那么 x=( d(v0,v1) , d(v0,v2) , , d(v0,vn) )是此系統(tǒng)的一可行解，其中 d(v0,vi)是約束圖中 v0 到 vi 的最短路徑(i=1,2,n)。如果 G 包含負權(quán)回路，那么此系統(tǒng)不存在可行解。差分約束問題的求解由上述定理可知，可以采用Bellman-Ford 算法對差分約束問題求解。因為在約束圖中，從源點 v0 到其他所有頂點間均存在邊，因此約束圖中任何負權(quán)回路均從 v0 可達。如果Bellman-Ford 算法返回 TRUE，則最短路徑權(quán)給出了此系統(tǒng)的一個可行

5、解；如果返回 FALSE，則差分約束系統(tǒng)無可行解。關(guān)于 n 個未知量m 個約束條件的一個差分約束系統(tǒng)產(chǎn)生出一個具有n+1 個頂點和n+m 條邊的約束圖。因此采用 Bellman-Ford 算法，可以再 O(n+1)(n+m)=O(n2+nm)時間內(nèi)將系統(tǒng)解決。此外，可以用 SPFA 算法進行優(yōu)化，復雜度為 O(km)，其中 k 為常數(shù)。http/JudgeOnline/problem?id=1364DescriptionOnce, in one kingdom, there was a queen andt queen was expecting a baby. Thequeen prayed

6、: If my child was a son and if only he was a sound king. After ninemonths her child was born, and, she gave birth to a nion.Unfortunay, as it used to happen in royal famis, the son was a little retarded.After many years of study he was able just to addeger numbers and to comparewhether the result is

7、 greater or lessn a giveneger number. In addition, thenumbers had to be written in a sequence and he was able to sum just continuoussubsequenof the sequence.The old king was very unhappy of his son. But he was ready to make everything toenable his son toern the kingdom after his death. With regards

8、to his sons skillshe decidedt every problem the king had to decide aboud to be presented ina form of a finite sequence ofeger numbers and the deciabout it would bedone by sing aneger constra(i.e. an upper or lower limit) for the sum oft sequence.his way there waseast some hopet his son would be able

9、to make some decis.After the old king died, the young king began to reign. But very soon, a lot of peoplebecame very unsatisfied with his decis and decided to dethrone him. They triedtot by provingt his decis were wrong.Therefore some conspirators presented to the young king a set of problemst hehad

10、 to decide about. The set of problems washe form of subsequenSi = aSi,aSi+1, ., aSi+ni of a sequen= a1, a2, ., an. The king thought a minuteand then decided, i.e. he set for the sum aSi + aSi+1 + . + aSi+ni of eachsubsequeni aneger constraki (i.e. aSi + aSi+1 + . + aSi+ni ki resp.) and declared thes

11、e constras as his decis.After a while he realizedt some of his decis were wrong. He could not revokethe declared constras but trying to save himself he decided to fake the sequencet he was given. He ordered to his advisors to find such a sequent wouldsatisfy the constras he set. Help the advisors of

12、 the king and write a programtdecides whether such a sequence exists or not.InputThe inponsists of blocks of lines. Each block except the last corresponds to oneset of problems and kings decis about them.heline of the block thereareegers n, and m where 0 n = 100 is length of the sequenand 0 m (coded

13、as gt) or operator (coded as lt) respectively. The symbols si, ni and ki have themeaning described above. The last block consists of just one line containing 0.OutputThe outpontains the lines corresponding to the blockshe input. A linecontains text sucsful conspiracy when such a sequence does not ex

14、ist. Otherwiseit contains text lamentable kingdom. There is no linehe outporresponding tothe last null block of the input.Sample Input4212 gt 022 lt 2121 0 gt 01 0 lt 00Sample Outputlamentable kingdomsucsful conspiracySourceCentral Europe 1997很典型的差分約束，關(guān)鍵在于怎么構(gòu)圖。這里設(shè) Sum(i) = A1 + A2 + + Ai-1那么輸入的 si n

15、i oi ki就可以轉(zhuǎn)換成如下的約束式：Sum(si+ni+1) - Sum(si) oi ki#include using namespatd;constMAXN = 120;constinf = 0 x7f;struct nodes,e,v;edgeMAXN;n,m,dMAXN;bool bellman_ford()i,j;for(i=0;i=n+1;i+) di=inf;for(d0=0,i=1;i=n+1;i+)for(j=0;j=(n+m);j+)if(dedgej.s+edgej.vdedgej.e)dedgej.e=dedgej.s+edgej.v;for(i=0;i=(n+m);i+)if(dedgei.s+edgei.vdedgei.e)return false;return true;main()char oi5;si,ni,k,i,j;while(scanf(%d,&n),n)scanf(%d,&m);for(i=0;im;i+)scanf(%d %d