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

1、飛行員配對(duì)問(wèn)題
二分圖匹配問(wèn)題，直接Hopcroft Karp即可。

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

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

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

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

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