<题目链接>
题目大意：
给你一张地图，地图上m代表人，H代表房子，现在所有人要走到房子内，且一个房子只能容纳一个人(人和房子的数量相同)，人每移动一步，需要花1美元，问所有人走到房子中的最小花费。
解题分析：
一个人对应一个房子，并且人与房子之间的花费相当于权值，很明显的最大权完美匹配，直接套用KM算法即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define INF 0x3f3f3f3f
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define mem(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define fi first
#define se second
const int N = ;
char str[];
typedef pair<int,int>pii;
int n,m,nx,ny;
int lx[N],ly[N];
int linker[N],slack[N],visx[N],visy[N],w[N][N];
pii locx[N],locy[N]; //记录二分图中x,y两部分所有点的坐标
inline int dis(pii tmp1,pii tmp2){ //计算两点之间的花费
return (abs(tmp1.fi-tmp2.fi)+abs(tmp1.se-tmp2.se));
}
bool DFS(int x){
visx[x]=;
rep(y,,ny){
if(visy[y])continue;
int tmp=lx[x]+ly[y]-w[x][y];
if(!tmp){
visy[y]=;
if(linker[y]==-||DFS(linker[y])){
linker[y]=x;
return true;
}
}else slack[y]=min(slack[y],tmp);
}
return false;
}
int KM(){
mem(linker,-);mem(ly,);
rep(i,,nx){
lx[i]=-INF;
rep(j,,ny)lx[i]=max(lx[i],w[i][j]);
}
rep(x,,nx){
rep(i,,ny)slack[i]=INF;
while(true){
mem(visx,);mem(visy,);
if(DFS(x))break;
int d=INF;
rep(i,,ny)if(!visy[i])d=min(d,slack[i]);
rep(i,,nx)if(visx[i])lx[i]-=d;
rep(i,,ny)
if(visy[i])ly[i]+=d;
else slack[i]-=d;
}
}
int res=;
rep(y,,ny)
if(linker[y]!=-)
res+=w[linker[y]][y];
return res;
}
int main(){
while(~scanf("%d%d",&n,&m),n||m){
nx=ny=;
rep(i,,n){
scanf("%s",str+);
rep(j,,m){
if(str[j]=='m')locx[++nx]=mp(i,j); //存下x,y两部分坐标
if(str[j]=='H')locy[++ny]=mp(i,j);
}
}
rep(i,,nx) rep(j,,ny){
w[i][j]=-dis(locx[i],locy[j]); //得到两点之间的最短距离,也就是人到对应的房子所需花的钱，因为最后要求最小花费，所以这里要先取反
}
printf("%d\n",(-)*KM()); //得到最小花费
}
}
2018-11-18