搭配飛行員

搭配飛行員：http://cogs.yeefan.us/cogs/problem/problem.php?pid=14
題解：建立虛擬源點(diǎn)匯點(diǎn)，然后水過
code：http://cogs.yeefan.us/cogs/submit/code.php?id=148410

數(shù)字梯形

數(shù)字梯形：http://cogs.yeefan.us/cogs/problem/problem.php?pid=738
題解：
規(guī)則(1)
把梯形中每一個(gè)位置抽象為兩個(gè)點(diǎn)（i.a）,（i.b），建立附加源S匯T。
1、對(duì)每一個(gè)點(diǎn)i從（i.a）到（i.b）連接1條容量為1，費(fèi)用為點(diǎn)i權(quán)值的有向邊。
2、從S向梯形頂層每一個(gè)（i.a）連1條容量為1，費(fèi)用為0的有向邊。
3、從梯形底層每一個(gè)（i.b）向T連1條容量為1，費(fèi)用為0的有向邊。
4、對(duì)每一個(gè)點(diǎn)i和下面的兩個(gè)點(diǎn)j，分別連1條從（i.b）到（j.a）容量為1，費(fèi)用為0的有向邊。
求最大費(fèi)用最大流，費(fèi)用流值就是結(jié)果。
規(guī)則(2)
把梯形中每一個(gè)位置看作1個(gè)點(diǎn)i，建立附加源S匯T。
1、從S向梯形頂層每一個(gè)i連1條容量為1，費(fèi)用為0的有向邊。
2、從梯形底層每一個(gè)i向T連1條容量為無窮大，費(fèi)用為0的有向邊。
3、對(duì)每一個(gè)點(diǎn)i和下面的兩個(gè)點(diǎn)j，分別連1條從i到j(luò)容量為1，費(fèi)用為點(diǎn)i權(quán)值的有向邊。
求最大費(fèi)用最大流，費(fèi)用流值就是結(jié)果。
規(guī)則(3)
把梯形中每一個(gè)位置看作1個(gè)點(diǎn)i，建立附加源S匯T。
1、從S向梯形頂層每一個(gè)i連1條容量為1，費(fèi)用為0的有向邊。
2、從梯形底層每一個(gè)i向T連1條容量為無窮大，費(fèi)用為0的有向邊。
3、對(duì)每一個(gè)點(diǎn)i和下面的兩個(gè)點(diǎn)j，分別連1條從i到j(luò)容量為無窮大，費(fèi)用為點(diǎn)i權(quán)值的有向邊。
求最大費(fèi)用最大流，費(fèi)用流值就是結(jié)果。
其實(shí)第2個(gè)和第3個(gè)都很好處理，就是第1個(gè)有些麻煩，對(duì)這個(gè)題，我們建立n排點(diǎn)還是比較好寫的

code：http://cogs.yeefan.us/cogs/submit/code.php?id=157717

負(fù)載平衡

負(fù)載平衡：http://cogs.yeefan.us/cogs/problem/problem.php?pid=741
題解：
首先求出所有倉(cāng)庫(kù)存貨量平均值，設(shè)第i個(gè)倉(cāng)庫(kù)的盈余量為A[i]，A[i] = 第i個(gè)倉(cāng)庫(kù)原有存貨量 - 平均存貨量。建立2分圖，把每一個(gè)倉(cāng)庫(kù)抽象為兩個(gè)節(jié)點(diǎn)Xi和Yi。增設(shè)附加源S匯T。
1、如果A[i]>0，從S向Xi連1條容量為A[i]，費(fèi)用為0的有向邊。
2、如果A[i]<0，從Yi向T連1條容量為-A[i]，費(fèi)用為0的有向邊。
3、每一個(gè)Xi向兩個(gè)相鄰頂點(diǎn)j，從Xi到Xj連接1條容量為無窮大，費(fèi)用為1的有向邊，從Xi到Y(jié)j連接1條容量為無窮大，費(fèi)用為1的有向邊。
求最小費(fèi)用最大流，最小費(fèi)用流值就是最少搬運(yùn)量。

code：http://cogs.yeefan.us/cogs/submit/code.php?id=157626