题目链接：
?id=2195
题目大意：
在一个N*M的矩阵中，有M个人和M个房子，每个人要安排一个房子，每个房子只能安排一个人。
而每个人移动一步需要一美元。那么问题来了：求为每个人安排房子移动所需要的金钱最小值是多
少。
思路：
做一个二分图，，一边为人，另一边为房子，如果把人和房子之间的距离作为边权的话，问题就变成
了求带权二分图最小权和的最佳匹配。这里我们为了方便计算，吧人和房子之间的距离的负值作为
边权，那么就变成了求带权二分图最大权和的最佳匹配，就是经典的二分图最佳匹配问题。用KM算
法解出最大权值和。取其相反，就得到了最小权和。关于KM算法的模板参考博文：
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>using namespace std;const int MAXN = 110;const int INF = 0xffffff0;struct Node{int x,y;}Man[MAXN],House[MAXN];int Dist(Node a,Node b){return -(abs(a.x-b.x) + abs(a.y-b.y));}int N,NX,NY;int Map[MAXN][MAXN];int link[MAXN],lx[MAXN],ly[MAXN],slack[MAXN];int visx[MAXN],visy[MAXN];int FindPath(int u){visx[u] = 1;for(int i = 1; i <= NY; ++i){if(visy[i])continue;int temp = lx[u] + ly[i] – Map[u][i];if(temp == 0){visy[i] = 1;if(link[i] == -1 || FindPath(link[i])){link[i] = u;return 1;}}else if(slack[i] > temp)slack[i] = temp;}return 0;}int KM(){memset(ly,0,sizeof(ly));memset(link,-1,sizeof(link));for(int i = 1; i <= NX; ++i){lx[i] = -INF;for(int j = 1; j <= NY; ++j)if(Map[i][j] > lx[i])lx[i] = Map[i][j];}for(int i = 1; i <= NX; ++i){for(int j = 1; j <= NY; ++j)slack[j] = INF;while(1){memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(FindPath(i))break;int d = INF;for(int j = 1; j <= NY; ++j)if(!visy[j] && d > slack[j])d = slack[j];for(int j = 1; j <= NX; ++j)if(visx[j])lx[j] -= d;for(int j = 1; j <= NY; ++j)if(visy[j])ly[j] += d;elseslack[j] -= d;}}int res = 0;for(int i = 1; i <= NY; ++i)if(link[i] > -1)res += Map[link[i]][i];return res;}int main(){int N,M,ManNum,HouseNum;char ch;while(~scanf("%d%d",&N,&M) && (N||M)){ManNum = HouseNum = 1;for(int i = 1; i <= N; ++i){getchar();for(int j = 1; j <= M; ++j){scanf("%c",&ch);if(ch == 'm'){Man[ManNum].x = i;Man[ManNum++].y = j;}else if(ch == 'H'){House[HouseNum].x = i;House[HouseNum++].y = j;}}}NX = NY = ManNum-1;for(int i = 1; i <= NX; ++i){for(int j = 1; j <= NY; ++j){Map[i][j] = Dist(Man[i],House[j]);}}printf("%d\n",-KM());}return 0;}
当你能爱的时候就不要放弃爱
