Mato is No.1

在二分圖最大匹配中，每個點(diǎn)（不管是X方點(diǎn)還是Y方點(diǎn)）最多只能和一條匹配邊相關(guān)聯(lián)，然而，我們經(jīng)常遇到這種問題，即二分圖匹配中一個點(diǎn)可以和多條匹配邊相關(guān)聯(lián)，但有上限，或者說，L_i表示點(diǎn)i最多可以和多少條匹配邊相關(guān)聯(lián)。

二分圖多重匹配分為二分圖多重最大匹配與二分圖多重最優(yōu)匹配兩種，分別可以用最大流與最大費(fèi)用最大流解決。

（1）二分圖多重最大匹配：
在原圖上建立源點(diǎn)S和匯點(diǎn)T，S向每個X方點(diǎn)連一條容量為該X方點(diǎn)L值的邊，每個Y方點(diǎn)向T連一條容量為該Y方點(diǎn)L值的邊，原來二分圖中各邊在新的網(wǎng)絡(luò)中仍存在，容量為1（若該邊可以使用多次則容量大于1），求該網(wǎng)絡(luò)的最大流，就是該二分圖多重最大匹配的值。

（2）二分圖多重最優(yōu)匹配：
在原圖上建立源點(diǎn)S和匯點(diǎn)T，S向每個X方點(diǎn)連一條容量為該X方點(diǎn)L值、費(fèi)用為0的邊，每個Y方點(diǎn)向T連一條容量為該Y方點(diǎn)L值、費(fèi)用為0的邊，原來二分圖中各邊在新的網(wǎng)絡(luò)中仍存在，容量為1（若該邊可以使用多次則容量大于1），費(fèi)用為該邊的權(quán)值。求該網(wǎng)絡(luò)的最大費(fèi)用最大流，就是該二分圖多重最優(yōu)匹配的值。

例題：
【1】POJ1698 Alice's Chance
將電影作為X方點(diǎn)，每一天作為Y方點(diǎn)（最多50周，每周7天，所以共設(shè)350個Y方點(diǎn)），若第i個電影可以在第j天搞就連邊(i, j)。每個X方點(diǎn)的L值為該電影總共要搞多少天，每個Y方點(diǎn)的L值為1（每天最多只能搞一個電影），然后求二分圖多重最大匹配，若能使所有從源點(diǎn)連向X方點(diǎn)的邊都滿流，則輸出Yes，否則輸出No。
【2】POJ2112 Optimal Milking
先預(yù)處理求出每兩個點(diǎn)（包括擠奶點(diǎn)和牛）間的最短距離，然后將所有擠奶點(diǎn)作為X方點(diǎn)（L值為該擠奶點(diǎn)最多可以容納多少牛），所有牛作為Y方點(diǎn)（L值為1），X_i和Y_j間邊的權(quán)值為這兩個點(diǎn)之間的最短距離（若這兩點(diǎn)間不存在路徑則此處無邊），然后問題就變成了求一個多重匹配，使得每個Y方點(diǎn)都有匹配點(diǎn)且匹配邊中權(quán)值的最大值最小。
可以枚舉最大邊權(quán)值S，然后，原圖中所有權(quán)值大于S的邊都要刪去。若此時圖中存在符合要求的多重匹配，則S合法否則S不合法。由于S的合法性是單調(diào)的，所以可以二分枚舉S。