PKU3169-Layout

題目：http://poj.org/problem?id=3169
有N(1000)隻牛站在數線上，座標x1,x2,...,xn、並且有x1<=x2<=...<=xn
以及給出ML(10000)條互相喜歡的關係，牛p喜歡牛q希望彼此距離不超過r
還有MD(10000)條互相討厭的關係、希望彼此距離至少超過s
問滿足條件的情形下，最大的xn-x1是多少？
如果條件矛盾輸出-1，答案無限大輸出-2


程式碼：(待補)
就是一個差分約束系統
首先把所有的條件用寫成不等式xi-xj<=w的形式：
喜歡的關係A B D：
xB-xA<=D
討厭的關係A B D：
xA-xB<= -D (xB-xA>=D)

並且注意座標由左至右的順序是隱性的約束，也要如下表達
(xi-1) - (xi) <= 0

構造約束圖，並利用Bellman-Ford算法依x1當單源求解到xn的最短路徑

為什麼可以轉化成最短路徑呢？請看如下最短路的「三角形不等式」

dist[i] <= dist[j]+adj[j][i]

如果dist數組裡存的全是最短路，那麼這對任何的i,j都會成立
(想一下鬆弛的過程就能明白)

稍加移項以後得到

dist[i] - dist[j] <= adj[j][i]

於是加上解的平移關係(全部同加常數d仍然滿足約束)
就不難想像dist數組會是差分約束系統的解了

至於為什麼存在負環(無最短路存在)能表示無解呢？下面簡敘算法導論的證明
如果有負權回路v1,v2,v3,...,vk (vk就是v1，繞回來而已)
那麼把不等式條列如下
dist[2] - dist[1] <= adj[1][2]
dist[3] - dist[2] <= adj[3][2]

...
dist[k-1] - dist[k-2] <= adj[k-2][k-1]
dist[1] - dist[k-1] <= adj[k-1][1] 

這些不等式滿足的話，那麼全部相加以後也得滿足才行

相加以後左式=0、右式是負數，得到

0 <= 負權 (矛盾)

故負權回路的約束圖代表該系統無解