解決思路
基本原理
該算法是通過給每個頂點一個標號（叫做頂標）來把求最大權匹配的問題轉化為求完備匹配的問題的。設頂點Xi的頂標為A[ i ]，頂點Yj的頂標為B[ j ]，頂點Xi與Yj之間的邊權為w[i,j]。在算法執行過程中的任一時刻，對於任一條邊(i,j)，A[ i ]+B[j]>=w[i,j]始終成立。
KM算法的正確性基於以下定理：
若由二分圖中所有滿足A[ i ]+B[j]=w[i,j]的邊(i,j)構成的子圖（稱做相等子圖）有完備匹配，那么這個完備匹配就是二分圖的最大權匹配。
首先解釋下什麼是完備匹配，所謂的完備匹配就是在二部圖中，X點集中的所有點都有對應的匹配且Y點集中所有的點都有對應的匹配，則稱該匹配為完備匹配。
這個定理是顯然的。因為對於二分圖的任意一個匹配，如果它包含於相等子圖，那么它的邊權和等於所有頂點的頂標和；如果它有的邊不包含於相等子圖，那么它的邊權和小於所有頂點的頂標和。所以相等子圖的完備匹配一定是二分圖的最大權匹配。
初始時為了使A[ i ]+B[j]>=w[i,j]恆成立，令A[ i ]為所有與頂點Xi關聯的邊的最大權，B[j]=0。如果當前的相等子圖沒有完備匹配，就按下面的方法修改頂標以使擴大相等子圖，直到相等子圖具有完備匹配為止。
我們求當前相等子圖的完備匹配失敗了，是因為對於某個X頂點，我們找不到一條從它出發的交錯路。這時我們獲得了一棵交錯樹，它的葉子結點全部是X頂點。現在我們把交錯樹中X頂點的頂標全都減小某個值d，Y頂點的頂標全都增加同一個值d，那么我們會發現：
1）兩端都在交錯樹中的邊(i,j)，A[ i ]+B[j]的值沒有變化。也就是說，它原來屬於相等子圖，現在仍屬於相等子圖。
2）兩端都不在交錯樹中的邊(i,j)，A[ i ]和B[j]都沒有變化。也就是說，它原來屬於（或不屬於）相等子圖，現在仍屬於（或不屬於）相等子圖。
3）X端不在交錯樹中，Y端在交錯樹中的邊(i,j)，它的A[ i ]+B[j]的值有所增大。它原來不屬於相等子圖，現在仍不屬於相等子圖。
4）X端在交錯樹中，Y端不在交錯樹中的邊(i,j)，它的A[ i ]+B[j]的值有所減小。也就說，它原來不屬於相等子圖，現在可能進入了相等子圖，因而使相等子圖得到了擴大。
5)到最後，X端每個點至少有一條線連著，Y端每個點有一條線連著，說明最後補充完的相等子圖一定有完備匹配。（若由二分圖中所有滿足A[ i ]+B[j]=w[i,j]的邊(i,j)構成的子圖（稱做相等子圖）有完備匹配，那么這個完備匹配就是二分圖的最大權匹配。）
現在的問題就是求d值了。為了使A[ i ]+B[j]>=w[i,j]始終成立，且至少有一條邊進入相等子圖，d應該等於：
Min{A[ i ]+B[j]-w[i,j] | Xi在交錯樹中，Yi不在交錯樹中}。
改進
以上就是KM算法的基本思路。但是樸素的實現方法，時間複雜度為O(n^4)——需要找O(n)次增廣路，每次增廣最多需要修改O(n)次頂標，每次修改頂標時由於要枚舉邊來求d值，複雜度為O(n^2)。實際上KM算法的複雜度是可以做到O(n^3)的。我們給每個Y頂點一個“鬆弛量”函式slack，每次開始找增廣路時初始化為無窮大。在尋找增廣路的過程中，檢查邊(i,j)時，如果它不在相等子圖中，則讓slack[j]變成原值與A[ i ]+B[j]-w[i,j]的較小值。這樣，在修改頂標時，取所有不在交錯樹中的Y頂點的slack值中的最小值作為d值即可。但還要注意一點：修改頂標後，要把所有的不在交錯樹中的Y頂點的slack值都減去d。
Kuhn－Munkras算法流程：
(1)初始化可行頂標的值；
(2)用匈牙利算法尋找完備匹配；
(3)若未找到完備匹配則修改可行頂標的值；
(4)重複(2)(3)直到找到相等子圖的完備匹配為止；
C代碼
KM算法和最大匹配（匈牙利算法）
2010.7.18
匈牙利算法的分析與運用：
匈牙利算法的精髓在於USED哈希數組的使用，下面是匈牙利算法的主要模組：
在原程式進行調用是也就是簡簡單單的一句話：
for i:=1 to n do begin fillchar(used,sizeof(used),0); if find(i) then inc(all); end;
注意
每一次找匹配時USED都是清0的，這是為了記錄什麼可以找，什麼不可以找，說白了，這個模組就是一個遞歸的過程，USED的套用就是為了限制遞歸過程中的尋找範圍，從而達到“不好則換，換則最好”，這裡的最好是“新換”中最好的。
匈牙利算法解題是極為簡單的，但是圖論的難並不是難在解答，而是建圖的過程，也難怪會有牛曰：用匈牙利算法，建圖是痛苦的，最後是快樂的。當然，我們這些◎#！◎◎也只能搞搞NOIP了，一般不會太難，所以此算法，極為好用。
KM算法：
最大流的KM算法，又算的上算法世界中的一朵奇葩了。
解決最大流問題可以使用“網路流”，但較為繁瑣，沒有KM來得痛快，
下面是KM算法的核心模組：
可以見出，該模組與匈牙利算法極為相似，差別便是:
if not vy[y] and (lx[x]+ly[y]=w[x,y])判斷語句了，這裡涉及到KM算法的思想，不再贅述，請自行“擺渡”之。
但是在源程式的調用過程更是煩雜：
總結起來便是：有機會就上，沒有機會創造機會也要上！
