题干：

   粘贴不过来。。。

题目大意：

    500*500带权格子，每行每列要确定一个值，使row[i]+col[j] >= val[i][j]，要使所有row值和col值的和最小

输出每行的row[i],和每列的col[i]。

解题报告：

    跑一边KM，自带着就把我们需要的期望值给求出来了。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
 
using namespace std;
const int MAXN = 505;
const int INF = 0x3f3f3f3f;
int line[MAXN][MAXN];
int ex[MAXN],ey[MAXN];
bool visx[MAXN];
bool visy[MAXN];
int nxt[MAXN];
int slack[MAXN];
int N;
bool dfs(int x) {
	visx[x] = 1;
	for (int y = 1; y <= N; ++y) {
		if (visy[y]) continue; 
		int tmp = ex[x] + ey[y] - line[x][y];
		if (tmp == 0) {
			visy[y] = 1;
			if (nxt[y] == -1 || dfs( nxt[y] )) {
				nxt[y] = x;
				return 1;
			}
		} 
		else if(slack[y] > tmp) slack[y] = tmp;
	}
	return 0;
}
int KM() {
	memset(nxt, -1, sizeof nxt);
	memset(ey, 0, sizeof ey);
	for (int i = 1; i <= N; ++i) {
		ex[i] = line[i][1];
		for (int j = 2; j <= N; ++j) {
			ex[i] = max(ex[i], line[i][j]);
		}
	}
	for (int i = 1; i <= N; ++i) {
		fill(slack, slack + N + 1, INF);
		while (1) {
			memset(visx, 0, sizeof visx);
			memset(visy, 0, sizeof visy);
			if (dfs(i)) break;
			int d = INF;
			for (int j = 1; j <= N; ++j)
				if (!visy[j]) d = min(d, slack[j]);
			for (int j = 1; j <= N; ++j) {
				if (visx[j]) ex[j] -= d;
				if (visy[j]) ey[j] += d;
				else slack[j] -= d;
			}
		}
	}
	int res = 0;
	for (int i = 1; i <= N; ++i) res += line[ nxt[i] ][i];
	return res;
}
int main() {
	while (~scanf("%d",&N)) {
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= N; ++j)
				scanf("%d", &line[i][j]);
		int ans = KM();
		for(int i = 1; i<=N; i++) {
			printf("%d%c",ex[i],i == N ? '\n' : ' ');
		}
		for(int i = 1; i<=N; i++) {
			printf("%d%c",ey[i],i == N ? '\n' : ' ');
		}
		printf("%d\n",ans);
	}
	return 0;
}