本文共 1781 字，大约阅读时间需要 5 分钟。
//http://www.cnblogs.com/IMGavin/#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;#define gets(A) fgets(A, 1e8, stdin)const int INF = 0x3F3F3F3F, N = 108, MOD = 1003;const double EPS = 1e-6;int val[N][N];bool visx[N], visy[N];//始终有lx[x] + ly[y] >= w[x][y]，且结束后顶标之和最小int lx[N], ly[N], slack[N], match[N];//match[y]表示Y集节点y对X的匹配int nx, ny;//X集Y集节点个数，要先初始化bool Hungary(int u){ visx[u] = true; for(int i = 0; i < ny; i++){ if(!visy[i]){ if(lx[u] + ly[i] == val[u][i]){ visy[i] = true; if(match[i] == -1 || Hungary(match[i])){ match[i] = u; return true; } }else{ slack[i] = min(slack[i], lx[u] + ly[i] - val[u][i]); } } } return false;}void KM(){ memset(match, -1, sizeof(match)); memset(lx, 0, sizeof(lx)); //初始化顶标 memset(ly, 0, sizeof(ly)); //ly[i]为0 //lx[i]为权值最大的边 for(int i = 0; i < nx; i++){ for(int j = 0; j < ny; j++){ lx[i] = max(lx[i], val[i][j]); } } for(int i = 0; i < nx; i++){ for(int j = 0; j < ny; j++){ slack[j] = INF; } while(1){ memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if(Hungary(i)){ break; }else{ int tp = INF; for(int j = 0; j < ny; j++){ if(!visy[j] && tp > slack[j]){ tp = slack[j]; } } for(int j = 0; j < nx; j++){ if(visx[j]){ lx[j] -= tp; } } for(int j = 0; j < ny; j++){ if(visy[j]){ ly[j] += tp; }else{ slack[j] -= tp; } } } } }}int main(){ int n; while(cin >> n){ nx = ny = n; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ scanf("%d", &val[i][j]); val[i][j] = -val[i][j]; } } KM(); int ans = 0; for(int i = 0; i < n; i++){ ans += val[match[i]][i]; } cout<<-ans<
转载于:https://www.cnblogs.com/IMGavin/p/6388134.html