Posted on 2011-03-26 21:53
Mato_No1 閱讀(3242)
評論(2) 編輯 收藏 引用 所屬分類:
網絡流
在二分圖最大匹配中，每個點（不管是X方點還是Y方點）最多只能和一條匹配邊相關聯，然而，我們經常遇到這種問題，即二分圖匹配中一個點可以和多條匹配邊相關聯，但有上限，或者說，Li表示點i最多可以和多少條匹配邊相關聯。
二分圖多重匹配分為二分圖多重最大匹配與二分圖多重最優匹配兩種，分別可以用最大流與最大費用最大流解決。
（1）二分圖多重最大匹配：
在原圖上建立源點S和匯點T，S向每個X方點連一條容量為該X方點L值的邊，每個Y方點向T連一條容量為該Y方點L值的邊，原來二分圖中各邊在新的網絡中仍存在，容量為1（若該邊可以使用多次則容量大于1），求該網絡的最大流，就是該二分圖多重最大匹配的值。
（2）二分圖多重最優匹配：
在原圖上建立源點S和匯點T，S向每個X方點連一條容量為該X方點L值、費用為0的邊，每個Y方點向T連一條容量為該Y方點L值、費用為0的邊，原來二分圖中各邊在新的網絡中仍存在，容量為1（若該邊可以使用多次則容量大于1），費用為該邊的權值。求該網絡的最大費用最大流，就是該二分圖多重最優匹配的值。
例題：
【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。