题意：一个N*N的矩阵，第i行第j列的元素大小为w[i][j]，每行求一个数row[i]，每列求一个数col[j]，使得row[i] + col[j] >= w[i][j]，且所有的row[]与所有的col[]和总和最小( N <= 500, 其它输入数为正整数且 <= 100)。
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2378
——>>row[i] + col[j] >= w[i][j]，这个恰恰是二分图最佳完美匹配的一个式子，所以，以行row为X结点，以列col为Y结点，权值即为对应元素w[i][j]的值建图，跑一次KM就好。
另外发现：用scanf(“%d”, &N) == 1比用~scanf(“%d”, &N)快了3ms。。。
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 500 + 10;
const int INF = 0x3f3f3f3f;
int N, w[maxn][maxn], lx[maxn], ly[maxn], fa[maxn];
bool S[maxn], T[maxn];
bool match(int i){
S[i] = 1;
for(int j = 1; j <= N; j++) if(lx[i] + ly[j] == w[i][j] && !T[j]){
T[j] = 1;
if(!fa[j] || match(fa[j])){
fa[j] = i;
return 1;
}
}
return 0;
}
void update(){
int a = INF;
for(int i = 1; i <= N; i++) if(S[i])
for(int j = 1; j <= N; j++) if(!T[j])
a = min(a, lx[i] + ly[j] - w[i][j]);
for(int i = 1; i <= N; i++){
if(S[i]) lx[i] -= a;
if(T[i]) ly[i] += a;
}
}
void KM(){
for(int i = 1; i <= N; i++){
fa[i] = lx[i] = ly[i] = 0;
for(int j = 1; j <= N; j++) lx[i] = max(lx[i], w[i][j]);
}
for(int i = 1; i <= N; i++)
while(1){
for(int j = 1; j <= N; j++) S[j] = T[j] = 0;
if(match(i)) break;
else update();
}
}
void read(){
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++) scanf("%d", &w[i][j]);
}
void solve(){
for(int i = 1; i < N; i++) printf("%d ", lx[i]); printf("%d\n", lx[N]);
for(int i = 1; i < N; i++) printf("%d ", ly[i]); printf("%d\n", ly[N]);
int sum = 0;
for(int i = 1; i <= N; i++) sum += lx[i] + ly[i];
printf("%d\n", sum);
}
int main()
{
while(scanf("%d", &N) == 1){
read();
KM();
solve();
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101184.html原文链接：https://javaforall.net
