本文主要是介绍hdu1533 going home 二分图最优匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二分图最优匹配
#include <iostream>
#include <string.h>
#include <cstdio>using namespace std;const int MAXN = 100 + 10;
const int INF = (~0U >> 1);char temp[MAXN][MAXN];
int c[MAXN][MAXN];
int lx[MAXN], ly[MAXN];
bool visx[MAXN], visy[MAXN];
int match[MAXN];
int row, col;
int numm, numh;struct Node
{int x, y;
}M[MAXN], H[MAXN];int abs(int x)
{return x < 0 ? -x : x;
}bool dfs(int u)
{visx[u] = true;for (int i = 0; i < numm; i++){if (!visy[i] && lx[u] + ly[i] - c[u][i] == 0){visy[i] = true;if (match[i] == -1 || dfs(match[i])){match[i] = u;return true;}}}return false;
}void solve()
{memset(ly, 0, sizeof(ly));memset(match, -1, sizeof(match));for (int i = 0; i < numm; i++){lx[i] = c[i][0];for (int j = 1; j < numm; j++){if (c[i][j] > lx[i]){lx[i] = c[i][j];}}}for (int i = 0; i < numm; i++){while (true){memset(visx, false, sizeof(visx));memset(visy, false, sizeof(visy));if (dfs(i)){break;}int inc = INF;for (int i = 0; i < numm; i++){if (visx[i]){for (int j = 0; j < numm; j++){if (!visy[j] && lx[i] + ly[j] - c[i][j] < inc){inc = lx[i] + ly[j] - c[i][j];}}}}for (int i = 0; i < numm; i++){if (visx[i]){lx[i] -= inc;}if (visy[i]){ly[i] += inc;}}}}int ans = 0;for (int i = 0; i < numm; i++){ans += c[match[i]][i];}cout << -ans << endl;
}void input()
{while (scanf("%d %d", &row, &col) && (row || col)){numm = numh = 0;for (int i = 0; i < row; i++){scanf("%s", temp[i]);for (int j = 0; j < col; j++){if (temp[i][j] == 'm'){M[numm].x = i;M[numm++].y = j;}else if (temp[i][j] == 'H'){H[numh].x = i;H[numh++].y = j;}}}for (int i = 0; i < numm; i++){for (int j = 0; j < numm; j++){c[i][j] = -(abs(M[i].x - H[j].x) + abs(M[i].y - H[j].y));}}solve();}
}int main()
{input();return 0;
}
这篇关于hdu1533 going home 二分图最优匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
