【ZZ】?KM算法-概述?：??
?KM算法是通過給每個頂點一個標(biāo)號（叫做頂標(biāo)）來把求最大權(quán)匹配的問題轉(zhuǎn)化為求完備匹配的問題的。設(shè)頂點Xi的頂標(biāo)為A，頂點Yi的頂標(biāo)為B，頂點Xi與Yj之間的邊權(quán)為w【i,j】。在算法執(zhí)行過程中的任一時刻，對于任一條邊(i,j)，A+B【j】>=w【i,j】始終成立。

KM算法-定理及思路???
KM算法的正確性基于以下定理：
　　若由二分圖中所有滿足A+B【j】=w【i,j】的邊(i,j)構(gòu)成的子圖（稱做相等子圖）有完備匹配，那么這個完備匹配就是二分圖的最大權(quán)匹配。
　　這個定理是顯然的。因為對于二分圖的任意一個匹配，如果它包含于相等子圖，那么它的邊權(quán)和等于所有頂點的頂標(biāo)和；如果它有的邊不包含于相等子圖，那么它的邊權(quán)和小于所有頂點的頂標(biāo)和。所以相等子圖的完備匹配一定是二分圖的最大權(quán)匹配。
　　初始時為了使A+B【j】>=w【i,j】恒成立，令A(yù)為所有與頂點Xi關(guān)聯(lián)的邊的最大權(quán)，B【j】=0。如果當(dāng)前的相等子圖沒有完備匹配，就按下面的方法修改頂標(biāo)以使擴(kuò)大相等子圖，直到相等子圖具有完備匹配為止。
　　我們求當(dāng)前相等子圖的完備匹配失敗了，是因為對于某個X頂點，我們找不到一條從它出發(fā)的交錯路。這時我們獲得了一棵交錯樹，它的葉子結(jié)點全部是X頂點。現(xiàn)在我們把交錯樹中X頂點的頂標(biāo)全都減小某個值d，Y頂點的頂標(biāo)全都增加同一個值d，那么我們會發(fā)現(xiàn)：
兩端都在交錯樹中的邊(i,j)，A+B【j】的值沒有變化。也就是說，它原來屬于相等子圖，現(xiàn)在仍屬于相等子圖。
??? 兩端都不在交錯樹中的邊(i,j)，A和B【j】都沒有變化。也就是說，它原來屬于（或不屬于）相等子圖，現(xiàn)在仍屬于（或不屬于）相等子圖。
X端不在交錯樹中，Y端在交錯樹中的邊(i,j)，它的A+B【j】的值有所增大。它原來不屬于相等子圖，現(xiàn)在仍不屬于相等子圖。
??? X端在交錯樹中，Y端不在交錯樹中的邊(i,j)，它的A+B【j】的值有所減小。也就說，它原來不屬于相等子圖，現(xiàn)在可能進(jìn)入了相等子圖，因而使相等子圖得到了擴(kuò)大。
　　現(xiàn)在的問題就是求d值了。為了使A+B【j】>=w【i,j】始終成立，且至少有一條邊進(jìn)入相等子圖，d應(yīng)該等于min{A+B【j】-w【i,j】|Xi在交錯樹中，Yi不在交錯樹中}。
　　以上就是KM算法的基本思路。但是樸素的實現(xiàn)方法，時間復(fù)雜度為O(n4)——需要找O(n)次增廣路，每次增廣最多需要修改O(n)次頂標(biāo)，每次修改頂標(biāo)時由于要枚舉邊來求d值，復(fù)雜度為O(n2)。實際上KM算法的復(fù)雜度是可以做到O(n3)的。我們給每個Y頂點一個“松弛量”函數(shù)slack，每次開始找增廣路時初始化為無窮大。在尋找增廣路的過程中，檢查邊(i,j)時，如果它不在相等子圖中，則讓slack【j】變成原值與A+B【j】-w【i,j】的較小值。這樣，在修改頂標(biāo)時，取所有不在交錯樹中的Y頂點的slack值中的最小值作為d值即可。但還要注意一點：修改頂標(biāo)后，要把所有的slack值都減去d。