KM算法 二分图最大权值匹配
#include <iostream> #include<cstring> #include<cstdio> #include<cmath> const int maxn = 356; const int INF = (1<<31)-1; int w[maxn][maxn]; int lx[maxn],ly[maxn]; int linky[maxn]; int visx[maxn],visy[maxn]; int slack[maxn]; int nx,ny; bool find(int x) { visx[x] = true; for(int y = 0; y < ny; y++) { if(visy[y]) continue; int t = lx[x] + ly[y] - w[x][y]; if(t==0) { visy[y] = true; if(linky[y]==-1 || find(linky[y])) { linky[y] = x; return true; } } else if(slack[y] > t) slack[y] = t; } return false; } int KM() { int i,j; memset(linky,-1,sizeof(linky)); memset(ly,0,sizeof(ly)); for(i = 0; i < nx; i++) for(j = 0,lx[i] = -INF; j < ny; j++) if(w[i][j] > lx[i]) lx[i] = w[i][j]; for(int x = 0; x < nx; x++) { for(i = 0; i < ny; i++) slack[i] = INF; while(true) { memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if(find(x)) break; int d = INF; for(i = 0; i < ny; i++) { if(!visy[i] && d > slack[i]) d = slack[i]; } for(i = 0; i < nx; i++) { if(visx[i]) lx[i] -= d; } for(i = 0; i < ny; i++) { if(visy[i]) ly[i] += d; else slack[i] -= d; } } } int result = 0; for(i = 0; i < ny; i++) if(linky[i]>-1) result += w[linky[i]][i]; return result; } int main() { int n; while(~scanf("%d",&n)) { nx=ny=n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) { int x; scanf("%d",&x); w[i][j]=x; } printf("%d ",KM()); } return 0; }