int main() {
while(scanf("%d", &n) != -1) {
solve();
}
return 0;
}

UVa 11383 - Golden Tiger Claw
有n*n的格子，每个格子有w(i, j)，现在给每行确定一个整数row(i) ，每列确定一个整数col(i)，使得所有w(i, j) <= row(i) + col(j)。
其实这样就相当于利用KM算法求最大权完美匹配。KM算法实际上最后求出的所有的lx, ly的和是最小的且都满足lx(i) + ly(j) >= w(i, j)，所以直接用KM算法来求解，这个应用还是挺灵活的。

[cpp]
/* **********************************************
Author : JayYe
Created Time: 2013-8-17 19:43:54
File Name : zzz.cpp
*********************************************** */

#include
#include

int max(int a, int b) { return a>b a:b; }
int min(int a, int b) { return a>b b:a; }

const int maxn = 500;

int n, match[maxn+10], lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10];
bool S[maxn+10], T[maxn+10];

bool dfs(int i) {
S[i] = 1;
for(int j = 1;j <= n; j++) if(!T[j])
slack[j] = min(slack[j], lx[i] + ly[j] - w[i][j]);
for(int j = 1;j <= n; j++) if(w[i][j] == lx[i] + ly[j] && !T[j]) {
T[j] = 1;
if(!match[j] || dfs(match[j])) {
match[j] = i;
return true;
}
}
return false;
}

void update() {
int delta = 1<<30;
for(int i = 1;i <= n ;i++) if(!T[i])
delta = min(delta, slack[i]);
for(int i = 1;i <= n; i++) {
if(S[i]) lx[i] -= delta;
if(T[i]) ly[i] += delta;
}
}

void KM() {
int i, j;
for(i = 1;i <= n; i++) {
lx[i] = ly[i] = match[i] = 0;
for(j = 1;j <= n; j++)
lx[i] = max(lx[i], w[i][j]);
}
for(i = 1;i <= n; i++) {
while(true) {
for(j = 1;j <= n; j++) S[j] = T[j] = 0, slack[j] = 1<<30;
if(dfs(i)) break;
else update();
}
}
}

void solve() {
int i, j;
for(i = 1;i <= n; i++)
for(j = 1;j <= n; j++) scanf("%d", &w[i][j]);
KM();
int ans = 0;
for(i = 1;i <= n; i++) printf("%d%c", lx[i], i < n ' ' : '\n'), ans += lx[i];
for(i = 1;i <= n; i++) printf("%d%c", ly[i], i < n ' ' : '\n'), ans += ly[i];
printf("%d\n", ans);
}

int main() {
while(scanf("%d", &n) != -1) {
solve();
}
return 0;
}

/* **********************************************
Author : JayYe
Created Time: 2013-8-17 19:43:54
File Name : zzz.cpp
*********************************************** */

#include
#include

int max(int a, int b) { return a>b a:b; }
int min(int a, int b) { return a>b b:a; }

const int maxn = 500;

int n, match[maxn+10], lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10];
bool S[maxn+10], T[maxn+10];

bool dfs(int i) {
S[i] = 1;
for(int j = 1;j <= n; j++) if(!T[j])
slack[j] = min(slack[j], lx[i] + ly[j] - w[i][j]);
for(int j = 1;j <= n; j++) if(w[i][j] == lx[i] + ly[j] && !T[j]) {
T[j] = 1;
if(!match[j] || dfs(match[j])) {
match[j] = i;
return true;
}
}
return false;
}

void update() {
int delta = 1<<30;
for(int i = 1;i <= n ;i++) if(!T[i])
delta = min(delta, slack[i]);
for(int i = 1;i <= n; i++) {
if(S[i]) lx[i] -= delta;
if(T[i]) ly[i] += delta;
}
}

void KM() {
int i, j;
for(i = 1;i <= n; i++) {
lx[i] = ly[i] = match[i] = 0;
for(j = 1;j <= n; j++)
lx[i] = max(lx[i], w[i][j]);
}
for(i = 1;i <= n; i++) {
while(true) {
for(j = 1;j <= n; j++) S[j] = T[j] = 0, slack[j] = 1<<30;
if(dfs(i)) break;
else update();
}
}
}

void solve() {
int i, j;
for(i = 1;i <= n; i++)
for(j = 1;j <= n; j++) scanf("%d", &w[i][j]);
KM();
int ans = 0;
for(i = 1;i <= n; i++) printf("%d%c", lx[i], i < n ' ' : '\n'), ans += lx[i];
for(i = 1;i <= n; i++) printf("%d%c", ly[i], i < n ' ' : '\n'), ans += ly[i];
printf("%d\n", ans);
}

int main() {
while(scanf("%d", &n) != -1) {
solve();
}
return 0;
}

UVa 1006 - Fixed Partition Memory Management

大概题意是有n个程序要让他们在m个内存区域里运行，一个内存区域不能同时进行两个程序，但是可以先运行完一个程序再运行下一个。转换成求最小权匹配，最后输出有点麻烦。