搭配飛行員

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

數字梯形

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

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

負載平衡

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

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