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