POJ2195 KM算法

View Code /*==================================================*\ | POJ2195 邊上有權值求取值最大(最小)的完全匹配 \*==================================================*/ int N,M, cntm,cnth; int slack[MM],lx[MM],ly[MM], pre[MM], maze[MM][MM]; bool sx[MM],sy[MM]; struct Point{ int x,y; }pointm[MM],pointh[MM];void get_data() {cntm=cnth=1;for(i=1;i<=N;i++) {scanf("%s",ch);for(j=0;ch[j];j++) {if(ch[j]=='m') pointm[cntm].x=i,pointm[cntm++].y=j+1;if(ch[j]=='H') pointh[cnth].x=i,pointh[cnth++].y=j+1;}} for(i=1;i<cntm;i++) {for(j=1;j<cnth;j++) {temp=f_abs(pointm[i].x-pointh[j].x)+f_abs(pointm[i].y-pointh[j].y);maze[i][j]=-temp; //求最小的完全匹配加上的是負值，求最大就加上正值 }} } bool dfs(int u) {int i,j,k,temp;sx[u]=true;for(i=1;i<cnth;i++) {if(sy[i]) continue;temp=lx[u]+ly[i]-maze[u][i];if(!temp) {sy[i]=true; if(pre[i]==-1||dfs(pre[i])) { pre[i]=u; return true; }}else if(slack[i]>temp) slack[i]=temp;}return false; }int bestmatch() { //返回權值最大(最小的完全匹配)int i,j,k;for(i=1;i<cntm;i++) {lx[i]=-inf; ly[i]=0;for(j=1;j<cnth;j++) {if(lx[i]<maze[i][j]) lx[i]=maze[i][j];}}memset(pre,-1,sizeof(pre));for(i=1;i<cntm;i++) {for(j=0;j<cntm;j++) slack[j]=inf;while(true) {memset(sx,false,sizeof(sx));memset(sy,false,sizeof(sy));if(dfs(i)) break;int dx=inf;for(j=1;j<cntm;j++) {if(!sy[j]&&dx>slack[j]) dx=slack[j];}for(j=1;j<cntm;j++) {if(sx[j]) lx[j]-=dx;if(sy[j]) ly[j]+=dx;if(!sy[j]) slack[j]-=dx; } }}int sum=0;for(i=1;i<cntm;i++) sum-=maze[pre[i]][i]; //求最小的完全匹配加上的是負值，求最大就加上正值 return sum; }

?

轉載于:https://www.cnblogs.com/zhang1107/archive/2012/12/12/2814881.html

總結

以上是生活随笔為你收集整理的KM算法模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。