题目大意：一张图中，有相等数量的“m” 和 “H” ，分别代表人和房子，要求通过移动人使最终每个房子里都有一个人，输出最小的移动步数。
解题思路：这题是求最小权值匹配，可用KM算法求解，需要注意的是，KM算法求的是最大权值匹配，这里需要把每条边的权值取反，得到最大权值匹配后，再把答案取反。
请看代码：
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define INF 0x7fffffff
using namespace std ;
const int MAXN = 300 ;
struct Node
{
int x ;
int y ;
} H[MAXN] , M[MAXN] ;
int Lx[MAXN] , Ly[MAXN] ;
bool visx[MAXN] , visy[MAXN] ;
int yy[MAXN] ;
int slack[MAXN] ;
int w[MAXN][MAXN] ;
char s[MAXN][MAXN] ;
int n , m ;
int mcnt , hcnt ;
int ans ;
void chu()
{
mem(visx , 0) ;
mem(visy , 0) ;
mem(yy , -1) ;
mcnt = hcnt = 0 ;
}
void init()
{
int i , j ;
for(i = 0 ; i < n ; i ++)
{
scanf("%s" , s[i]) ;
for(j = 0 ; j < m ; j ++)
{
if(s[i][j] == 'm')
{
M[mcnt].x = i ;
M[mcnt ++].y = j ;
}
else if(s[i][j] == 'H')
{
H[hcnt].x = i ;
H[hcnt ++].y = j ;
}
}
}
}
int dis(Node a , Node b)
{
return abs(a.x - b.x) + abs(a.y - b.y) ;
}
void buildG()
{
int i , j ;
for(i = 0 ; i < mcnt ; i ++)
{
for(j = 0 ; j < hcnt ; j ++)
{
w[i][j] = -1 * dis(M[i] , H[j]) ;
}
}
}
int dfs(int u)
{
visx[u] = 1 ;
int v ;
for(v = 0 ; v < hcnt ; v ++)
{
if(visy[v]) continue ;
int t = Lx[u] + Ly[v] - w[u][v] ;
if(t == 0)
{
visy[v] = 1 ;
if(yy[v] == -1 || dfs(yy[v]))
{
yy[v] = u ;
return 1 ;
}
}
else
{
if(slack[v] > t)
slack[v] = t ;
}
}
return 0 ;
}
int KM()
{
int i ;
int MAX ;
for(i = 0 ; i < mcnt ; i ++)
{
MAX = -1 * INF ;
for(int j = 0 ; j < hcnt ; j ++)
{
if(MAX < w[i][j])
MAX = w[i][j] ;
}
Lx[i] = MAX ;
}
mem(Ly , 0) ;
for(i = 0 ; i < mcnt ; i ++)
{
for(int j = 0 ; j < hcnt ; j ++)
{
slack[j] = INF ;
}
while (1)
{
mem(visx , 0) ; // 每次dfs前都要初始化 ！！
mem(visy , 0) ;
if(dfs(i))
break ;
int d = INF ;
int k ;
for(k = 0 ; k < hcnt ; k ++)
{
if(!visy[k] && d > slack[k])
{
d = slack[k] ;
}
}
for(k = 0 ; k < hcnt ; k ++)
{
if(visx[k])
{
Lx[k] -= d ;
}
if(visy[k])
{
Ly[k] += d ;
}
if(!visy[k])
{
slack[k] -= d ;
}
}
}
}
ans = 0 ;
for(i = 0 ; i < mcnt ; i ++)
{
ans += w[ yy[i] ][i] ;
}
}
void solve()
{
buildG() ;
KM() ;
printf("%d\n" , ans * (-1)) ;
}
int main()
{
while (scanf("%d%d" , &n , &m) != EOF)
{
if(n == 0 && m == 0)
break ;
chu() ;
init() ;
solve() ;
}
return 0 ;
}