首页 > 代码库 > 二分图带权匹配-Kuhn-Munkres算法模板 [二分图带权匹配]

二分图带权匹配-Kuhn-Munkres算法模板 [二分图带权匹配]

尴尬。。。理解不太好T T


 

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 #define inf 0x3f3f3f3f 7  8 const int maxn=1005; 9 10 int n;11 //标杆序号 12 int lx[maxn],ly[maxn];13 //是否被搜索过 14 bool sx[maxn],sy[maxn];15 int weight[maxn][maxn],mat[maxn];16 17 inline int maxx(const int &n1,const int &n2){18     return n1>n2?n1:n2;19 }20 21 bool dfs(int x){22     sx[x]=1;23     for(int i=0;i<n;i++)24         if(!sy[i]&&lx[x]+ly[i]==weight[x][i]){25             sy[i]=1;26             if(mat[i]==-1||dfs(mat[i])){27                 mat[i]=x;28                 return 1;29             }30         }31     return 0;32 }33 34 //x==0最小35 //x==1最大 36 int KM(int flag){37     if(!flag)38         for(int i=0;i<n;i++)39             for(int j=0;j<n;j++)40                 weight[i][j]=-weight[i][j];41     memset(mat,-1,sizeof mat);42     //初始化标杆 43     for(int i=0;i<n;i++){44         lx[i]=-inf;45         ly[i]=0;46         for(int i=0;i<n;i++)47             for(int j=0;j<n;j++)48                 lx[i]=maxx(lx[i],weight[i][j]);49     }50     for(int i=0;i<n;i++)51         while(1){52             memset(sx,0,sizeof sx);53             memset(sy,0,sizeof sy);54             if(dfs(i))  break;55             //修改标杆 56             int mic=inf;57             for(int j=0;j<n;j++)58                 if(sx[j])59                     for(int k=0;k<n;k++)60                         if(!sy[k]&&lx[j]+ly[k]-weight[j][k]<mic)61                             mic=lx[j]+ly[k]-weight[j][k];62             if(mic==0)  return -1;63             for(int j=0;j<n;j++){64                 if(sx[j])  lx[j]-=mic;65                 if(sy[j])  ly[j]+=mic;66             }67             for(int j=0;j<n;j++)68                 printf("%d ",lx[j]);69             puts("");70             for(int j=0;j<n;j++)71                 printf("%d ",ly[j]);72             puts("\n");73         }74     int sum=0;75     for(int i=0;i<n;i++)76         if(mat[i]>=0)77             sum+=weight[mat[i]][i];78     if(!flag)  sum=-sum;79     return sum;80 }81 82 int main(){83     scanf("%d",&n);84     for(int i=0;i<n;i++)85         for(int j=0;j<n;j++)86             scanf("%d",&weight[i][j]);87     printf("%d\n",KM(1));88     return 0;89 }90 /*91 592 3 4 6 4 993 6 4 5 3 894 7 5 3 4 295 6 3 2 2 596 8 4 5 4 797 98 KM(1)=2999 */

 

二分图带权匹配-Kuhn-Munkres算法模板 [二分图带权匹配]