在Acm論文中看到的，一起學習一下，至少解決了我不少疑問。
3．3 例題3——Layout
題意簡述：
當排隊等候喂食時，奶牛喜歡和它們的朋友站得靠近些。FJ有N（2<=N<=1000）頭奶牛，編號從1到N，沿一條直線站著等候喂食。奶牛排在隊伍中的順序和它們的編號是相同的。因為奶牛相當苗條，所以可能有兩頭或者更多奶牛站在同一位置上。即使說，如果我們想象奶牛是站在一條數軸上的話，允許有兩頭或更多奶牛擁有相同的橫坐標。
一些奶牛相互間存有好感，它們希望兩者之間的距離不超過一個給定的數L。另一方面，一些奶牛相互間非常反感，它們希望兩者間的距離不小於一個給定的數D。給出ML條關於兩頭奶牛間有好感的描述，再給出MD條關於兩頭奶牛間存有反感的描述。（1<=ML,MD<=10000，1<=L,D<=1000000）
你的工作是：如果不存在滿足要求的方案，輸出-1；如果1號奶牛和N號
奶牛間的距離可以任意大，輸出-2；否則，計算出在滿足所有要求的情況下，1號奶牛和N號奶牛間可能的最大距離。
分析：
如果當前問題比較復雜，我們應該學會“退一步”思考，由簡單到復雜。
求最大值不知從何下手，我們先從容易的開始分析。
我們先研究，如果不要求輸出1和N的最大距離，而只需一個可行的距離，應該如何操作。
我們用D[i]表示I號奶牛和1號奶牛間的距離。
因為在隊伍中的順序必須和編號相同，所以對於任意I號奶牛，1<=I<N，在距離上應該滿足：
D[I+1] - D[I] >= 0
對於每個好感的描述(i，j，k)，假設i<=j，體現到距離上的要求就是：
D[j] - D[I] <= k
對於每個反感的描述(i，j，k)，假設i<=j，體現到距離上的要求就是：
D[j] - D[I] >= k
這時的模型有一個名稱，叫作：差分約束系統。
為了方便起見，我們將每種不等式寫成我們約定的形式：
D[I] <= D[I+1]
D[j] <= D[I] + k
D[I] <= D[j] - k
看到這些不等式，你想到了什麼？
沒錯，在求頂點間地最短路問題中，我們有這樣的不等式：
若頂點u到頂點v有邊e=uv，且邊權為w(e)，設d(u),d(v)為源點到頂點u和頂點v的最短路長，
則 d(v) <= d(u) + w(e)
這個不等式和前面的條件形式十分相似，這就啟發我們用構圖用最短路做。
具體步驟是：
作有向圖G=(V,E)，V={ v1，v2，v3，…，vn}，E={e1，e2，e3，…}，對於相鄰兩點i和(i+1)，對應的頂點vi+1向vi引一條邊，費用為0；對於每組好感描述(ai，bi，di)，我們假設有ai<bi，否則ai和bi交換，則頂點vai向vbi引一條邊，費用為di；對於每組反感描述(ai，bi，di)，我們假設有ai<bi，否則ai和bi交換，則頂點vbi向vai引一條邊，費用為-di。
於是問題變為在G中求v1到其它所有頂點的最短路。我們證明若G中無負權回路，則問題有解，即存在滿足條件的數列，若G中有負權回路，則問題無解，即不存在滿足條件的數列。
定理5 問題是否有解等價於圖G是否沒有負權回路。
證明：若G中無負權回路，我們可以求出v1其他頂點u的最短路長，設為d(u)。由於是最短路，因此對於任意邊eE，e=uv，有d(u)+w(e)>=d(v)，從而所有的約束條件都被滿足，問題一定有解。若G中有負權回路，說明在任何時刻，G中至少有一個點v的最短路長可以更新，因此必須存在一條邊e=uv，使得d(u)+w(e)<d(v)。所以無論何時，都會有某個約束條件不被滿足，問題無解。（證畢）
檢測負權回路，可以用Bellman-Ford算法。
回到原問題。
先說說考試時我的做法。
將所有點的最短路估計值設為一個充分大的值，v1的最短路估計值設為0。然後運行一次Bellman-Ford。
如果圖G中有負權回路，那麼輸出-1；
否則，如果標號為N的頂點的最短路估計仍為一個充分大的值，那麼它和標號為1的頂點間的距離可以任意大，這時輸出-2；
如果以上兩種情況都不滿足，那麼輸出標號為N的點的最短路徑估計值。
什麼是充分大呢？
只需要比原圖中最大的邊權×頂點數還大就行了。
因為只要無圈，每個頂點最多只會被經過一次，所以肯定比這個值小，所以在該圖中，我們可以把這個值看作是無窮大。
該方法可以通過競賽的所有測試數據。
考試的時候，我沒有去刻意證明這個方法的正確性，只是感覺它應該可行。
現在讓我們從理論上證明它。
定理6 若運行Bellman-Ford後，標號為N的頂點的最短路估計值仍為充分大，那麼N和1的距離可以任意大。
證明：從剛才的操作可以看出，到了這一步，已經把含有負權回路的情況排除掉了。在圖G中，該充分大的值比可能得到的最大距離大，因此，它和任意大的值對於G的效果都是一樣的（同樣大於合法的最大距離）。由於充分大的值在G中滿足約束，所以任意大的值亦滿足約束，從而距離可以任意大。（證畢）
剩下還有一個問題。
定理7 若運行Bellman-Ford後，標號為N的頂點的最短路估計值比充分大小，那麼它是N和1可能的最大距離。
證明：設D[i]是頂點i和1的最短路徑估計值，d[i]是頂點i和1可能的最大距離。
我們首先證明，d[n]<=D[n]，運用反證法。
假如d[n]>D[n]，那麼在Bellman-Ford運行之前，將賦予每個頂點i的充分大的值換成對應的d[i]。由於d本身滿足所有約束條件，所以運行後，得出D'=d。由於充分大的值比所有d[i]都大，而求最短路運用的是逐步松弛操作，我們設立一個更大的初值不可能導致我們的終值反而更小。所以對於任意i，必定有D[i]>=D'[i]，即有D[n]>=d[n]，這與我們的假設矛盾。
然後我們證明，d[n]>=D[n]。
根據d[i]的定義，它是i和1的可能最大距離。由於D[i]是滿足題目的所有約束的，所以D[i]是頂點i和1可能的距離。如果D[i]>d[i]，那麼與d[i]的定義矛盾。www.2cto.com
綜合上述，有D[i]=d[i]。從而D[n]是n和1可能的最大距離。（證畢）
運行Bellman-Ford最壞情況下的復雜度是O((ML+MD)*N)=O(2*107)，可以在規定時間內出解。另外，實際運行的速度相當理想，大部分數據運行基本上不需要時間。
作者：zhang20072844
