題干：

? ?粘貼不過來。。。

題目大意：

? ? 500*500帶權(quán)格子，每行每列要確定一個值，使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; }

?

總結(jié)

以上是生活随笔為你收集整理的【UVA - 11383】Claw Golden Tiger （二分图最优匹配，KM算法原理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。