题意：此乃第一道真正意义上的最大权值匹配，其他题目其实都是求一个最小权值匹配。
代码如下：
#include#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;int N;int w[305][305];int lx[305], ly[305];int sx[305], sy[305];int match[305], slack[305];int path(int u) { sx[u] = 1; for (int i = 1; i <= N; ++i) { if (sy[i]) continue; int t = lx[u] + ly[i] - w[u][i]; if (!t) { sy[i] = 1; if (!match[i] || path(match[i])) { match[i] = u; return true; } } else { slack[i] = min(slack[i], t); } } return false;}void KM() { memset(match, 0, sizeof (match)); memset(ly, 0, sizeof (ly)); memset(lx, 0, sizeof (lx)); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { lx[i] = max(lx[i], w[i][j]); } } for (int i = 1; i <= N; ++i) { memset(slack, 0x3f, sizeof (slack)); while (1) { memset(sx, 0, sizeof (sx)); memset(sy, 0, sizeof (sy)); if (path(i)) break; int d = INF; for (int j = 1; j <= N; ++j) { if (!sy[j]) d = min(d, slack[j]); } for (int j = 1; j <= N; ++j) { if (sx[j]) lx[j] -= d; if (sy[j]) ly[j] += d; else slack[j] -= d; } } } int ret = 0; for (int i = 1; i <= N; ++i) { ret += w[match[i]][i]; } printf("%d\n", ret);}int main() { while (scanf("%d", &N) != EOF) { for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { scanf("%d", &w[i][j]); } } KM(); } return 0; }