大概一個星期前小豬發(fā)給我一份網(wǎng)絡(luò)流24題，直到昨天才開始做。

1、飛行員配對問題
二分圖匹配問題，直接Hopcroft Karp即可。

2、太空飛行計劃問題
題目大意是有M個實驗，有N個儀器，每個實驗需要一個或多個儀器，做實驗有收益，購買儀器需要消耗，求收益最多的方案。
最大權(quán)閉合圖問題。設(shè)源點匯點為S、T，從S向M個實驗連一條容量為所得收益的有向邊，N個儀器向T連一條容量為所需消耗的有向邊，另外，從某個實驗向所需要的儀器連一條無窮大的有向邊。
求該圖最小割為MinCut，設(shè)所以實驗的收益為TOT，則答案為TOT-MinCut。

3、最小路徑覆蓋問題
對于一個有向無環(huán)圖，將每個頂點X，拆成X1、X2，如果原圖中有一條有向邊<X,Y>，則在X1、Y2之間連一條邊，答案即為原圖中頂點數(shù)減去該二分圖的最大匹配數(shù)。

4、魔術(shù)球問題
題目大意是給出N個柱子，在這些柱子上依次放入編號為1、2、3……的球，要求一個柱子上相鄰兩個數(shù)的和為完全平方數(shù)，求最多可以放置多少個球。
順序枚舉可以放入的球數(shù)，將每個數(shù)字看作一個頂點，如果i+j(i<j)為完全平方數(shù)，則從i向j連一條有向邊，最終的圖為有向無環(huán)圖，求此圖的最小路徑覆蓋。枚舉直到ans的最小路徑覆蓋為N，ans+1的最小路徑覆蓋為N+1。

5、圓桌問題
題目大意是有N個代表團，第i個代表團有r[i]個人，有M個圓桌，第i個圓桌可容納c[i]個人，同一個代表團的不能坐在一起，求一種安排方案。
二分圖多重匹配問題。從S向N個代表團各連一條容量為r[i]的邊，每個代表團向M個圓桌連一條容量為1的邊，每個圓桌向T連一條容量為c[i]的邊，如果網(wǎng)絡(luò)流的最大流為代表團總?cè)藬?shù)，則存在這樣的方案。

7、試題庫問題
題目大意是有N道試題，共有K種類型，每道試題可能屬于一個或多個類別，現(xiàn)要求選出M道試題，使第i種類型題數(shù)為need[i]。求一種方案。
二分圖多重匹配問題。設(shè)S、S'、T，從S向S'連一條容量為M的邊，從S'向每道試題連一條容量為1的邊，對于試題i，如果屬于類型j，則從試題i向類型j連一條容量為1邊，每個類型向T連一條容量為need[j]的邊。如果網(wǎng)絡(luò)流的最大流為M，則存在這樣的方案。