poj 1275 3159 1364 1716 1201 3169
這類問題，就像網絡流，圖論，dp，關鍵在列出滿足的表達式，建立好數學模型，剩下的過程就很簡單了。所以主要難點在于構圖，從實際的描述抽象成模型。準確找到約束條件。
關于基礎知識可以查看clrs 22.4節(jié)。下面只介紹我遇到的一些問題和理解。
所謂的差分約束系統(tǒng)，實際上指一系列的表達式，滿足 形如{ xi - xj <= a}
求解實際上轉化成了圖論里的一個等價問題，最短路問題，實際上巧妙的利用了最短路具有的性質 di - dj <= w(j,i)
如果這樣的最短路求成來了，他們的值便可以直接作為xi xj的一組可行解。
圖論里求最短路，有很多方法，差分約束系統(tǒng)，一般利用的是單源最短路，而在單源最短路算法中，常見的是dijkstra和bellman-ford算法。這兩個算法各有優(yōu)劣。
dijkstra算法，效率比較高，如果用堆實現，可以達到O(vlogv+E)的復雜度,但是它只能解決正邊權類型的問題，對于負邊權的問題，必須采用bellman-ford算法，它的復雜度是VE.
bellman-ford算法很強大，不單可以求最短路，還可以求最長路。一般如果約束條件是 <=形式的，就標志著要求最短路，>=則要通過求最長路解決。
當然這兩種約束是可以轉化的，因為 xi - xj <= a實際上等價于xj- xi >= a。
一.優(yōu)化途徑：
1.如果改變邊的松弛(relax)順序，程序的執(zhí)行順序會有很多改觀
2.當所有邊都不能再松弛的時候，便可以跳出循環(huán)了，不必全部循環(huán)V-1次
這些可以通過poj1716 1201體驗到
二.關于Dist[]的初始化化
1.如果將源點到各點的距離初始化為0，最終求出的最短路滿足 它們之間相互最接近了
2.如果將源點到各點的距離初始化為INF(無窮大)，其中之1為0，最終求出的最短路滿足 它們與該點之間相互差值最大。
這些可以從poj3169 layout 得到證實。
三.
關于dikstra算法的堆實現，有兩種策略，一種是一開始把全部節(jié)點放到堆里，為每個節(jié)點維護一個在堆里的索引數組。另一種策略是當當前點被更新才放到堆里，但是要注意標記已經求得最短路的哪些點，避免重復求值。
我采用的是第一種策略，去求解的poj3159 Candies
當然還有一個優(yōu)化是，如果已經找到了目標點，就可以退出了，不必全部求出最短路
四.陷阱
int a[MAX] = {INF};
注意a里面的元素只有第一個會被賦為INF,其他會被賦為0，而不是INF。
關于模型的建立，其實，很多情況下我們的 xi都是一個和式，比如從開頭到現在的某個量的積累值，比如poj1716 1201中，我們要定義x[i]為點集里小于i的數的個數，則x[j] - x[i]則表示了落在線段區(qū)間[i,j]的點的個數。還有poj1364 King 也是類似，另外一些可能就是比較簡單的直接的約束關系。
比較復雜的如poj1275 Cashier Employment
這個問題比較特殊，乍看其他上述問題都是尋找最小數目的點，使這些點可以覆蓋線段。而這個則是找一些數目的人，而人實際上是一些線段，使這些線段可以在那些特點的總數目可以滿足要求并且數目最少。關鍵在定義一個狀態(tài)，這里如果大膽定義i時刻出納員數目s[i]，就可以了，然后利用這個s[i]便可以找到所有的約束關系，并列出不等式，這樣模型就建立好了。
這個可以參考劉汝佳的書P307，圖論最短路那部分，剛好以這個問題為例，而且這個問題求的就是最長路。對于sum可以二分進行優(yōu)化，不過我直接窮舉也過了。
poj3159 Candies
這是我接觸差分約束的第一題。設S[a]為kid a獲得的candies數，則每一行代表的約束是S[b]-S[a]<=c，目標函數是使得S=S[N]-S[1]最大。
利用差分約束的思想建圖，對于每一條約束，從a向b做一條長為c的邊，則從1到N的最短路即為所求。由于本題c皆為非負數，所以可以用Dijkstra高效解決。