本文共 2924 字，大约阅读时间需要 9 分钟。
题意：给定一个矩阵，其中包含了一些人和房子（人数和房子数相等），每个人的目标是进入一个房子。每走一步花费1美金，要求所有人都能进入房子的最小花费。这是一个典型的二分图带权匹配问题。
这题的关键在于如何建图。对于每个人的每个位置，我们需要找到他到所有房子的最短距离，然后将这些距离作为边权重连接到房子节点。具体来说，我们可以使用BFS遍历每个人的所有可能移动路径，记录他到每个房子的最短距离。遍历完每个人的房子后，就可以建立起二分图的结构。
需要注意的是，KM算法是用来求最大权匹配的，而我们需要的是最小权匹配。因此，在使用KM算法时，我们需要将所有边的权重取相反数，最后再取反得到最小权匹配的结果。如果图中存在完美匹配，那么只需要将权重取相反数即可。如果存在不完美匹配，则需要在KM算法中进行一定的调整。
接下来，我们来看代码实现部分：
#include#include #include #include #define maxn 500using namespace std;char group[101][101];int index[101][101];struct pos { int x, y;} people[maxn], house[maxn];struct edge { int to, cap;} g[maxn];vector g[maxn];int a, b, sum_m, sum_h;const int mir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };int vis[101][101];struct step { int x, y, s;} now, next;void bfs(int sx, int sy, int ex, int ey) { memset(vis, 0, sizeof(vis)); step now, next; now.x = sx, now.y = sy, now.s = 0; vis[sx][sy] = 1; queue q; q.push(now); while (!q.empty()) { now = q.front(); q.pop(); if (now.x == ex && now.y == ey) { add_edge(index[sx][sy], index[now.x][now.y], ~now.s + 1); return; } for (int i = 0; i < 4; i++) { int x = now.x + mir[i][0]; int y = now.y + mir[i][1]; if (x >= 0 && y >= 0 && x < maxn && y < maxn) { if (!vis[x][y]) { vis[x][y] = 1; next.x = x, next.y = y, next.s = now.s + 1; q.push(next); } } } }}int x[maxn], y[maxn], link[maxn], sx[maxn], sy[maxn];slack;bool dfs(int t) { sx[t] = 1; for (int i = 0; i < g[t].size(); i++) { edge e = g[t][i]; if (!sy[e.to]) { int tmp = x[t] + y[e.to] - e.cap; if (tmp > 0) { sy[e.to] = 1; link[e.to] = -1; if (dfs(link[e.to])) { link[e.to] = t; return 1; } } } } slack = tmp; return 0;}void km() { j; for (int w = 0; w < sum_m; w++) { x[w] = 0; for (int v = 0; v < g[w].size(); v++) { if (g[w][v].cap > x[w]) { x[w] = g[w][v].cap; } } } for (int j = 0; j < sum_h; j++) { y[j] = 0; } memset(link, -1, sizeof(link)); for (int i = 0; i < sum_m; i++) { while (1) { memset(sx, 0, sizeof(sx)); memset(sy, 0, sizeof(sy)); slack = 0xfffffff; if (dfs(i)) break; for (int j = 0; j < sum_m; j++) { if (sx[j]) { x[j] -= slack; } } for (int j = 0; j < sum_h; j++) { if (sy[j]) { y[j] += slack; } } } }}int main() { while (scanf("%d%d", &a, &b) != EOF && a && b) { init(); for (int i = 0; i < maxn; i++) { gets(group[i]); for (int j = 0; j < g[i].size(); j++) { if (group[i][j] == 'H') { people[sum_m].x = i; people[sum_m].y = j; index[i][j] = sum_h; sum_m++; } else { house[sum_h].x = i; house[sum_h].y = j; sum_h++; } } } for (int n = 0; n < sum_m; n++) { for (int m = 0; m < sum_h; m++) { bfs(people[n].x, people[n].y, house[m].x, house[m].y); } } km(); int ans = 0, coun = 0; for (int i = 0; i < sum_h; i++) { int t = link[i]; if (t != -1) { coun++; ans += g[t][i].cap; } } printf("%d\n", ans); } return 0;}
这个代码的主要步骤是：
通过将边权重取相反数再求最大权匹配，可以得到最小权匹配的结果。
转载地址：http://sdxfk.baihongyu.com/