KM算法的正確性基于以下定理：

若由二分圖中所有滿足A[i]+B[i]=w[i][j]的邊C（i，j）構(gòu)成的子圖（即相等子圖）有完備匹配，那么這個(gè)完備匹配就是二分圖的最大權(quán)匹配

基本概念

1.完備匹配

設(shè)G=<V1,V2,E>為二分圖，|V1|<=|V2|,M為G中的一個(gè)最大匹配，且|M|=V1,則稱M為V1到V2的完備匹配。

通俗的理解，就是把V1中所有的點(diǎn)都匹配完

?2.可行頂標(biāo)

對(duì)于左邊的點(diǎn)設(shè)為L(zhǎng)X[maxn]數(shù)組，右邊的點(diǎn)設(shè)為L(zhǎng)Y[maxn]數(shù)組，w[i][j]表示 v[i] 到 v[j] 的權(quán)值

3.相等子圖

相等子圖為完備匹配中所有的匹配，即全部V1中的點(diǎn)和與V1中的點(diǎn)匹配的V2中的點(diǎn)，但是邊只包含 LX[i]+LY[j]=W[i][j]的邊

4.最優(yōu)完備匹配

最優(yōu)完備匹配就是在完備匹配的條件下求解權(quán)值最大或者最小，若由二分圖中所有滿足A[i]+B[i]=W[i][j]的邊C（i，j）構(gòu)成的相等子圖有完備匹配，那么這個(gè)完備匹配就是二分圖的最大權(quán)匹配

因?yàn)閷?duì)于二分圖的任意一個(gè)匹配，如果它包含相等子圖，那么它的邊權(quán)和等于所有頂點(diǎn)的頂標(biāo)和；如果它有邊不包含于相等子圖，那么它的邊權(quán)和小于所有頂點(diǎn)的頂標(biāo)和，所以相等子圖的完備匹配，一定是二分圖的最大權(quán)匹配。

5.交錯(cuò)樹(shù)

對(duì)V1中的一個(gè)頂點(diǎn)進(jìn)行匹配的時(shí)候，所標(biāo)記過(guò)的V1，V2中的點(diǎn)以及連線，形成一個(gè)樹(shù)狀的圖

KM算法原理

1.基本原理

該算法是通過(guò)給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)(叫做頂標(biāo)）來(lái)把求最大權(quán)匹配的問(wèn)題轉(zhuǎn)化為求完備匹配的問(wèn)題。
設(shè)頂點(diǎn)V1的頂標(biāo)lx[i]，V2頂點(diǎn)的頂標(biāo)為L(zhǎng)Y[j],頂點(diǎn)V1的i與V2的j之間的邊權(quán)為V(i,j)。在算法執(zhí)行的過(guò)程中，對(duì)于任一條邊C(i,j)，LX[i]+LY[i]>=V[i,j]始終成立

2.基本流程

（1）初始化時(shí)為了使 LX[i] + LY[j] >= V [i,j]恒成立，將V1的點(diǎn)的標(biāo)號(hào)記為與其相連的最大邊權(quán)值，V2的點(diǎn)標(biāo)號(hào)記為0
（2）用匈牙利算法在相等子圖尋找完備匹配
（3）若未找到完備匹配，則修改可行頂標(biāo)的值，擴(kuò)充相等子圖
（4）重復(fù)（2）（3）直到找到相等子圖的完備匹配為止

3.這里值得注意的是找完備匹配不難理解，主要是進(jìn)行可行頂標(biāo)的修改擴(kuò)充相等子圖

引用：

樸素的實(shí)現(xiàn)方法：時(shí)間復(fù)雜度為O(n4)——需要找O(n)次增廣路， 每次增廣最多需要修改O(n)次頂 標(biāo)，每次修改頂標(biāo)時(shí)由于要枚舉邊來(lái)求d值，復(fù)雜度為O(n2)。

實(shí)際上KM算法的復(fù)雜度是可以做到O(n3)的。我們給每個(gè)Y頂點(diǎn)一個(gè)“松弛量”函數(shù) slack，每次開(kāi)始找增廣路時(shí)初始化為無(wú)窮大。在尋找增廣路的過(guò)程中，檢查邊(i,j)時(shí)，如果它不在相等子圖中，則讓slack[j]變成原值與A [i]+B[j]-w[i,j]的較小值。這樣，在修改頂標(biāo)時(shí)，取所有不在交錯(cuò)樹(shù)中的Y頂點(diǎn)的slack值中的最小值作為d值即可。但還要注意一點(diǎn)：修改 頂標(biāo)后，要把所有的slack值都減去d。

引用：

如果當(dāng)前的相等子圖沒(méi)有完備匹配，就按下面的方法修改頂標(biāo)以使擴(kuò)大相等子圖，直到相等子圖具有完備匹配為止。

我們求當(dāng)前相等子圖的完備匹配失敗了，是因?yàn)閷?duì)于某個(gè)V1頂點(diǎn)，我們找不到一條從它出發(fā)的交錯(cuò)路。這時(shí)我們獲得了一棵交錯(cuò)樹(shù)，它的葉子結(jié)點(diǎn)全部是V1頂點(diǎn)。現(xiàn)在我們把交錯(cuò)樹(shù)中V1頂點(diǎn)的頂標(biāo)全都減小某個(gè)值d，V2頂點(diǎn)的頂標(biāo)全都增加同一個(gè)值d，那么我們會(huì)發(fā)現(xiàn)：

1）兩端都在交錯(cuò)樹(shù)中的邊(i,j)，lx[ i ]+ly[j]的值沒(méi)有變化。也就是說(shuō)，它原來(lái)屬于相等子圖，現(xiàn)在仍屬于相等子圖。

2）兩端都不在交錯(cuò)樹(shù)中的邊(i,j)，lx[ i ]和ly[j]都沒(méi)有變化。也就是說(shuō)，它原來(lái)屬于（或不屬于）相等子圖，現(xiàn)在仍屬于（或不屬于）相等子圖。

3）V1端不在交錯(cuò)樹(shù)中，V2端在交錯(cuò)樹(shù)中的邊(i,j)，它的lx[ i ]+ly[j]的值有所增大。它原來(lái)不屬于相等子圖，現(xiàn)在仍不屬于相等子圖。

4）V1端在交錯(cuò)樹(shù)中，V2端不在交錯(cuò)樹(shù)中的邊(i,j)，它的lx[ i ]+ly[j]的值有所減小。也就說(shuō)，它原來(lái)不屬于相等子圖，現(xiàn)在可能進(jìn)入了相等子圖，因而使相等子圖得到了擴(kuò)大。

//HDU2255 #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 310 #define INF 0x3f3f3f3f #define clr(x) memset(x,0,sizeof(x)) int w[maxn][maxn];//w[i][j]表示i到j(luò)的權(quán)值 int lx[maxn],ly[maxn];//同時(shí)調(diào)節(jié)兩個(gè)數(shù)組，使得權(quán)值和最大 int n; //n1,n2為二分圖的頂點(diǎn)集，其中x屬于n1,y屬于n2 //link記錄n2中的點(diǎn)y在n1中所匹配的x點(diǎn)的編號(hào) int link[maxn]; int slack[maxn];//松弛操作 int visx[maxn],visy[maxn]; bool dfs(int x) {visx[x]=1;//得到發(fā)生矛盾的居民集合//對(duì)于這個(gè)居民，每個(gè)房子都試一下，找到就退出for(int y=1;y<=n;y++){if(visy[y]) continue;//不需要重復(fù)訪問(wèn)int t=lx[x]+ly[y]-w[x][y];//這個(gè)條件下使用匈牙利算法if(t==0)//標(biāo)志這個(gè)房子可以給這個(gè)居民{visy[y]=1; //這個(gè)房子沒(méi)人住或者可以讓住著個(gè)房子的人去找另外的房子住if(link[y]==0||dfs(link[y])){link[y]=x;return 1;//可以讓這位居民住進(jìn)來(lái)}}else if(slack[y]>t)//否則這個(gè)房子不能給這位居民slack[y]=t;}return 0; } int KM() {clr(lx);clr(ly);clr(link);//首先把每個(gè)居民出的錢(qián)最多的那個(gè)房子給他for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(lx[i]<w[i][j])lx[i]=w[i][j];//在滿足上述條件之后，給第i位居民分配房子for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)slack[j]=INF;//松弛量while(1)//直到給這個(gè)居民找到房子為止{clr(visx);clr(visy);if(dfs(i)) break;//找到房子，就跳出循環(huán)int d=INF;for(int k=1;k<=n;k++)if(!visy[k]&&d>slack[k])d=slack[k];//找到最小松弛量for(int k=1;k<=n;k++)//松弛操作，使發(fā)生矛盾的居民有更多選擇{if(visx[k]) lx[k]-=d;//將矛盾居民的要求降低，使發(fā)生矛盾的居民有更多if(visy[k]) ly[k]+=d;//使發(fā)生矛盾的房子在下一個(gè)子圖，保持矛盾}}}int ans=0;for(int i=1;i<=n;i++)ans+=w[link[i]][i];return ans; } int main() {while(~scanf("%d",&n)){clr(w);//每個(gè)案例都重置為0for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&w[i][j]);//輸入每條邊的權(quán)值printf("%d\n",KM());}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的二分图最大权匹配 KM算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。