学了下km算法....
写了道题
然后一遍过了2333
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1007;
int kind[maxn][maxn];
int match[maxn],ex_gril[maxn],ex_boy[maxn],vis_b[maxn],vis_g[maxn];
int n,slack[maxn];
bool dfs(int g) {
vis_g[g] = 1;
for(int i = 1;i <= n;++ i) {
if(vis_b[i]) continue;
int res = ex_gril[g] + ex_boy[i] - kind[g][i];
if(!res) {
vis_b[i] = true;
if(match[i] == -1|| dfs(match[i])) {
match[i] = g; return true;
}
} else slack[i] = std::min(slack[i],res);
}
return false;
}
int km() {
memset(match,-1,sizeof match) ;
memset(ex_boy,0,sizeof ex_boy);
for(int i = 1;i <= n;++ i) {
ex_gril[i] = kind[i][1];
for(int j = 1;j <= n;++ j)
ex_gril[i] = std::max(ex_gril[i],kind[i][j]);
}
for(int i = 1;i <= n;++ i) {
fill(slack + 1,slack + n + 1,INF);
while(11101001) {
memset(vis_g,0,sizeof vis_g);
memset(vis_b,0,sizeof vis_b);
if(dfs(i)) break;
int d = INF;
for(int j = 1;j <= n;++ j) if(!vis_b[j]) d = std::min(d,slack[j]);
for(int j = 1;j <= n;++ j) {
if(vis_g[j]) ex_gril[j] -= d;
if(vis_b[j]) ex_boy[j] += d;
else slack[j] -= d;
}
}
}
int ret = 0;
for(int i = 1;i <= n;++ i) ret += kind[match[i]][i];
return ret;
}
int main() {
while(scanf("%d",&n) == 1) {
for(int i = 1;i <= n;++ i)
for(int j = 1;j <= n;++ j)
scanf("%d",&kind[i][j]);
printf("%d
",km());
}
return 0;
}