首页 > 代码库 > 二分图带权匹配-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算法模板 [二分图带权匹配]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。