题意：n*m的方格中有p个房子和p个人，人走一步花费1元，要求每个人都要找到一个房子，且每个房子里只能有一个人，问p个人都找到各自的房子，最小的花费是多少。
思路：以每个人到所有房子的曼哈顿距离的相反数为权值建边，套下KM就是最小权匹配。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn = 505; const int INF = 0x3f3f3f3f; struct node { int x, y; node() {} node(int xx, int yy): x(xx), y(yy) {} }a[maxn], b[maxn]; // int nx, ny; int match[maxn], lx[maxn], ly[maxn], slack[maxn]; int visx[maxn], visy[maxn], w[maxn][maxn]; int Hungary(int x) { visx[x] = 1; for(int y = 1; y <= ny; y++) { if(visy[y]) continue; int temp = lx[x]+ly[y]-w[x][y]; if(temp == 0) { visy[y] = 1; if(match[y] == -1 || Hungary(match[y])) { match[y] = x; return 1; } } else if(slack[y] > temp) slack[y] = temp; } return 0; } int KM() { memset(match, -1, sizeof(match)); memset(ly, 0, sizeof(ly)); for(int i = 1; i <= nx; i++) lx[i] = -INF; for(int i = 1; i <= nx; i++) for(int j = 1; j <= ny; j++) if(w[i][j] > lx[i]) lx[i] = w[i][j]; for(int x = 1; x <= nx; x++) { for(int i = 1; i <= ny; i++) slack[i] = INF; while(1) { memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if(Hungary(x)) break; int d = INF; for(int i = 1; i <= ny; i++) if(!visy[i] && d > slack[i]) d = slack[i]; for(int i = 1; i <= nx; i++) if(visx[i]) lx[i] -= d; for(int i = 1; i <= ny; i++) if(visy[i]) ly[i] += d; else slack[i] -= d; } } int res = 0; for(int i = 1; i <= ny; i++) if(match[i] != -1) res += w[match[i]][i]; return res; } int main(void) { int n, m; while(cin >> n >> m && n+m) { char ch; int cnt1 = 1, cnt2 = 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { scanf(" %c", &ch); if(ch == 'm') a[cnt1++] = node(i, j); if(ch == 'H') b[cnt2++] = node(i, j); } nx = ny = cnt1-1; for(int i = 1; i <= nx; i++) for(int j = 1; j <= nx; j++) w[i][j] = -abs(a[i].x-b[j].x)-abs(a[i].y-b[j].y); printf("%d\n", -KM()); } return 0; } Sample Input 2 2 .m H. 5 5 HH..m ..... ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... 0 0 Sample Output 2 10 28
