参见这里
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, a[305][305], mat[305], exu[305], exv[305], qiw[305];
const int oo=0x3f3f3f3f;
bool viu[305], viv[305];
bool dfs(int x){
viu[x] = true;
for(int i=1; i<=n; i++){
if(viv[i]) continue;
int gap=exu[x]+exv[i]-a[x][i];
if(!gap){
viv[i] = true;
if(!mat[i] || dfs(mat[i])){
mat[i] = x;
return true;
}
}
else qiw[i] = min(qiw[i], gap);
}
return false;
}
int main(){
while(scanf("%d", &n)!=EOF){
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d", &a[i][j]);
memset(mat, 0, sizeof(mat));
memset(exu, 0, sizeof(exu));
memset(exv, 0, sizeof(exv));
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
exu[i] = max(exu[i], a[i][j]);
for(int i=1; i<=n; i++){
memset(qiw, 0x3f, sizeof(qiw));
while(true){
memset(viu, 0, sizeof(viu));
memset(viv, 0, sizeof(viv));
if(dfs(i)) break;
int tmp=oo;
for(int j=1; j<=n; j++)
if(!viv[j])
tmp = min(tmp, qiw[j]);
for(int j=1; j<=n; j++){
if(viu[j]) exu[j] -= tmp;
if(viv[j]) exv[j] += tmp;
else qiw[j] -= tmp;
}
}
}
int ans=0;
for(int i=1; i<=n; i++)
ans += a[mat[i]][i];
printf("%d
", ans);
}
return 0;
}