1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | // ** Start of PerfectMatch *******************************// Name: PerfectMatch by Kuhn_Munkras O(n^3)// Description: w is the adjacency matrix, nx,ny are the size of x and y,// lx, ly are the lables of x and y, fx[i], fy[i] is used for marking// whether the i-th node is visited, matx[x] means x match matx[x],// maty[y] means y match maty[y], actually, matx[x] is useless,// all the arrays are start at 1int nx,ny,w[MAXN][MAXN],lx[MAXN],ly[MAXN];int fx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];int path(int u){ int v; fx[u]=1; for(v=1;v<=ny;v++) if((lx[u]+ly[v]==w[u][v])&&(fy[v]<0)) { fy[v]=1; if((maty[v]<0)||(path(maty[v]))) { matx[u]=v; maty[v]=u; return(1); } // end of if((maty[v]... } // end of if((lx[u]... return(0);} // end of int path()int PerfectMatch(){ int ret=0,i,j,k,p; memset(ly,0,sizeof(ly)); for(i=1;i<=nx;i++) { lx[i]=-INF; for(j=1;j<=ny;j++) if(w[i][j]>lx[i]) lx[i]=w[i][j]; } // end of for(i... memset(matx,-1,sizeof(matx)); memset(maty,-1,sizeof(maty)); for(i=1;i<=nx;i++) { memset(fx,-1,sizeof(fx)); memset(fy,-1,sizeof(fy)); if(!path(i)) { i--; p=INF; for(k=1;k<=nx;k++) if(fx[k]>0) for(j=1;j<=ny;j++) if((fy[j]<0)&&(lx[k]+ly[j]-w[k][j]<p)) p=lx[k]+ly[j]-w[k][j]; for(j=1;j<=ny;j++) ly[j]+=(fy[j]<0?0:p); for(k=1;k<=nx;k++) lx[k]-=(fx[k]<0?0:p); } // end of if(!path(i)) } // end of for(i... for(i=1;i<=ny;i++) ret+=w[maty[i]][i]; return ret;} // end of int PerfectMatch()// ** End of PerfectMatch ********************************* |