题目链接
http://poj.org/problem?id=2195
题意 在一张N * M 的地图上 有 K 个人 和 K 个房子 地图上每个点都是认为可行走的 求 将每个人都分配到不同的房子 求他们的总的最小步数
思路 因为每个点都是可行走的 我们可以直接根据坐标 算出 每个人都不同房子的路径 然后用 KM 算法跑一下就可以了
KM算法 参考
https://blog.csdn.net/thundermrbird/article/details/52231639 https://blog.csdn.net/pi9nc/article/details/12250247
AC代码
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<map> #include<set> #include<string> #include<list> #include<stack> #include <queue> #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef long long ll; typedef pair <int, int> pii; const int INF = 0x3f3f3f3f; const int maxn = 1e2 + 5; const int MOD = 1e9; int nx, ny; int linker[maxn], lx[maxn], ly[maxn]; int g[maxn][maxn]; int slack[maxn]; bool visx[maxn], visy[maxn]; bool DFS(int x) { visx[x] = true; for (int y = 0; y < ny; y++) { if (visy[y]) continue; int tmp = lx[x] + ly[y] - g[x][y]; if (tmp == 0) { visy[y] = true; if (linker[y] == -1 || DFS(linker[y])) { linker[y] = x; return true; } } else if (slack[y] > tmp) slack[y] = tmp; } return false; } int KM() { CLR(linker, -1); CLR(ly, 0); for (int i = 0; i < nx; i++) { lx[i] = -INF; for (int j = 0; j < ny; j++) { if (g[i][j] > lx[i]) lx[i] = g[i][j]; } } for (int x = 0; x < nx; x++) { for (int i = 0; i < ny; i++) { slack[i] = INF; } while (true) { CLR(visx, false); CLR(visy, false); if (DFS(x)) break; int d = INF; for (int i = 0; i < ny; i++) { if (!visy[i] && d > slack[i]) d = slack[i]; } for (int i = 0; i < nx; i++) { if (visx[i]) lx[i] -= d; } for (int i = 0; i < ny; i++) { if (visy[i]) ly[i] += d; else slack[i] -= d; } } } int res = 0; for (int i = 0; i < ny; i++) if (linker[i] != -1) res += g[linker[i]][i]; return res; } int dis(int x1, int y1, int x2, int y2) { int x = abs(x1 - x2); int y = abs(y1 - y2); return x + y; } int main() { int n, m; while (scanf("%d%d", &n, &m) && (n || m)) { vector <pii> p, h; p.clear(); h.clear(); char c; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf(" %c", &c); if (c == 'm') p.push_back (pii(i, j)); if (c == 'H') h.push_back (pii(i, j)); } } int len = p.size(); for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { g[i][j] = -dis(p[i].first, p[i].second, h[j].first, h[j].second); //printf("%d\n", g[i][j]); } } nx = ny = len; printf("%d\n", -KM()); } }转载于:https://www.cnblogs.com/Dup4/p/9433102.html
相关资源：JAVA上百实例源码以及开源项目