對(duì)KM的深入理解請(qǐng)看以下博客（寫的不錯(cuò)的）：http://blog.sina.com.cn/s/blog_691ce2b701016reh.html

我的理解：如有錯(cuò)誤，請(qǐng)大牛指正！！

1.KM（）算法實(shí)際就是一種遍歷，從權(quán)值最大的開始匹配，如果成功的完備匹配了，那這個(gè)權(quán)值一定是最大的權(quán)值。因?yàn)槲覀兪菑淖畲蟮拈_始一點(diǎn)點(diǎn)小下來遍歷的。

2.slack[ ?] ?這個(gè)數(shù)組 可以說是一個(gè) 松弛變量數(shù)組 ，目的是為了 增加匹配。

3.實(shí)際也沒什么好講的就是不斷的增廣，很多也都這樣，松弛迫近，跟那什么單純形法有想通之處。

4. 匈牙利算法進(jìn)行匹配的尋找。

hdu 2255

#include<cstdio> #include<iostream> #include<cstring> using namespace std;const int M=400,inf=0x3f3f3f3f; int w[M][M],link[M],lx[M],ly[M]; int nx,ny,n,slack[M]; int visx[M],visy[M];int DFS(int x){visx[x]=1;int i;for(i=1;i<=ny;i++){if(visy[i]) continue;int t=lx[x]+ly[i]-w[x][i];if(t==0){visy[i]=1;if(link[i]==-1||DFS(link[i])){link[i]=x;return 1;}}else if(slack[i]>t) slack[i]=t;}return 0; }int KM() {int i,j;memset(link,-1,sizeof(link));memset(ly,0,sizeof(ly));for(i=1;i<=nx;i++)for(j=1,lx[i]=-inf;j<=ny;j++){if(lx[i]<w[i][j]) lx[i]=w[i][j];}for(i=1;i<=nx;i++){for(j=1;j<=ny;j++) slack[j]=inf; while(1){memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(DFS(i)) break;int d=inf;for(j=1;j<=ny;j++) if(!visy[j]&&slack[j]<d)d=slack[j];for(j=1;j<=nx;j++)if(visx[j]) lx[j]-=d;for(j=1;j<=ny;j++)if(visy[j])ly[j]+=d;elseslack[j]-=d;}}int res=0;for(i=1;i<=ny;i++){if(link[i]>-1)res+=w[link[i]][i];}return res; } int main() {int i,j;while(scanf("%d",&n)!=EOF){nx=ny=n;for(i=1;i<=nx;i++)for(j=1;j<=ny;j++)scanf("%d",&w[i][j]);printf("%d\n",KM());}return 0; }

總結(jié)

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

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