Posted on 2011-03-26 21:53
Mato_No1 閱讀(3249)
評論(2) 編輯 收藏 引用 所屬分類:
網絡流
在二分圖最大匹配中，每個點（不管是X方點還是Y方點）最多只能和一條匹配邊相關聯(lián)，然而，我們經常遇到這種問題，即二分圖匹配中一個點可以和多條匹配邊相關聯(lián)，但有上限，或者說，Li表示點i最多可以和多少條匹配邊相關聯(lián)。
二分圖多重匹配分為二分圖多重最大匹配與二分圖多重最優(yōu)匹配兩種，分別可以用最大流與最大費用最大流解決。
（1）二分圖多重最大匹配：
在原圖上建立源點S和匯點T，S向每個X方點連一條容量為該X方點L值的邊，每個Y方點向T連一條容量為該Y方點L值的邊，原來二分圖中各邊在新的網絡中仍存在，容量為1（若該邊可以使用多次則容量大于1），求該網絡的最大流，就是該二分圖多重最大匹配的值。
（2）二分圖多重最優(yōu)匹配：
在原圖上建立源點S和匯點T，S向每個X方點連一條容量為該X方點L值、費用為0的邊，每個Y方點向T連一條容量為該Y方點L值、費用為0的邊，原來二分圖中各邊在新的網絡中仍存在，容量為1（若該邊可以使用多次則容量大于1），費用為該邊的權值。求該網絡的最大費用最大流，就是該二分圖多重最優(yōu)匹配的值。
例題：
【1】POJ1698 Alice's Chance
將電影作為X方點，每一天作為Y方點（最多50周，每周7天，所以共設350個Y方點），若第i個電影可以在第j天搞就連邊(i, j)。每個X方點的L值為該電影總共要搞多少天，每個Y方點的L值為1（每天最多只能搞一個電影），然后求二分圖多重最大匹配，若能使所有從源點連向X方點的邊都滿流，則輸出Yes，否則輸出No。
【2】POJ2112 Optimal Milking
先預處理求出每兩個點（包括擠奶點和牛）間的最短距離，然后將所有擠奶點作為X方點（L值為該擠奶點最多可以容納多少牛），所有牛作為Y方點（L值為1），X
i和Y
j間邊的權值為這兩個點之間的最短距離（若這兩點間不存在路徑則此處無邊），然后問題就變成了求一個多重匹配，使得每個Y方點都有匹配點且匹配邊中權值的最大值最小。
可以枚舉最大邊權值S，然后，原圖中所有權值大于S的邊都要刪去。若此時圖中存在符合要求的多重匹配，則S合法否則S不合法。由于S的合法性是單調的，所以可以二分枚舉S。