题目链接
http://poj.org/problem?id=2195
题意
给定n个人和n个房子，每个房子只能住一个人（但可以停留若干人）。
给定一个N*M的矩阵，‘H’表示房子，’m‘表示人，’.’表示空地。每个人可以往上、下、左、右四个方向走，走一步的费用是1.求每个人都找到一个房子住下的最少花费。
分析
一个人匹配一个房子，联系到二分图最大权匹配。权值为人到房子的花费，即曼哈顿距离。
建立一个以人为X部，房子为Y部，权值为两者的曼哈顿距离的二分图。跑一遍KM算法即可。
刷网络流专题遇到的这题。所以我没用二分图最大权匹配解。
分析下题意，可以发现这是一个多源点多汇点费用流模型。因为一个房子只能住一个人，所以连一条从源点到人容量为1、费用为0的有向弧，连一条从房子到汇点容量为1、费用为0的有向弧。
又因为每个结点可以同时容纳多人，即结点容量为无穷大，故结点与结点之间的有向弧的容量为无穷大、费用为1.而每个结点可以往四个方向走，故连四个由该结点指出的有向弧。
求费用流，可以用SPFA在残量网络中不停找最短路，距离指标为费用。
AC代码
//79ms 0.6MB
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
//建图所用
const int maxn=1e4+100;
const int maxe=1e4+1000;
const int maxv=1e4+100;
struct edge
{
int to,w,next,c;//w是费用，c是残量网络的流量
}e[maxe<<1];
int head[maxv<<1],depth[maxv],cnt;
void init()
{
memset(head,-1,sizeof(head));
cnt=-1;
}
void add_edge(int u,int v,int w,int c)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].c=c;
e[cnt].next=head[u];
head[u]=cnt;
}
void _add(int u,int v,int w,int c)
{
add_edge(u,v,w,c);
add_edge(v,u,-w,0);
}
//费用流算法
int S,T;
int vis[maxn],dis[maxn],pre_v[maxn],pre_e[maxn];
bool spfa()//类似于EK算法，通过不停的找增广路,找一条距离最小的路径
{
memset(vis,0,sizeof(vis));
queue<int> que;
memset(dis,0x3f,sizeof(dis));//初始距离为无穷大
dis[S]=0;
que.push(S);
vis[S]=1;
while(!que.empty())//bfs
{
int u=que.front();que.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if(e[i].c>0 && dis[v]>dis[u]+e[i].w)//w表示费用，c表示残量网络的流量
{
dis[v]=dis[u]+e[i].w;//距离指标是费用
pre_e[v]=i;//记录前驱边，即记录增广路
pre_v[v]=u;//记录前驱点
if(!vis[v])//bfs
{
vis[v]=1;
que.push(v);
}
}
}
}
if(dis[T]<INF) return true;
return false;
}
int augment()//调整残量网络并返回增广路的费用
{
int flow=INF;//flow最终为当前增广路的流量
int u=T;
while(u!=S)//从汇点到源点逆着bfs中得到的路径走
{
flow=min(flow,e[pre_e[u]].c);//最大流是增广路流量的最小值
u=pre_v[u];
}
u=T;
while(u!=S)
{
e[pre_e[u]].c-=flow;//将增广路上的流量都减去最大流
e[pre_e[u]^1].c+=flow;
u=pre_v[u];
}
return flow*dis[T];//dis[T]表示T到汇点的距离，距离指标是费用
}
int cost()
{
int ans=0,cur=0;
while(spfa())//不停的找增广路
{
ans+=augment();//累加增广路的费用
}
return ans;
}
int n,m;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
bool valid(int x,int y)
{
return x>=1 && x<=n && y>=1 && y<=m;
}
int getid(int x,int y)
{
return (x-1)*m+y;
}
char s[maxn][maxn];
void build()
{
for(int i=1; i<=n; i++)
scanf("%s",(s[i]+1));
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
if(s[i][j]=='H')
_add(S,getid(i,j),0,1);//源点到房子
else if(s[i][j]=='m') //人到汇点
_add(getid(i,j),T,0,1);
for(int k=0; k<4; k++)
{
int fi=i+dir[k][0],fj=j+dir[k][1];
if(valid(fi,fj))
{
_add(getid(i,j),getid(fi,fj),1,INF);//每个结点可向四个方向流，容量为无穷大（一条边可走无数次），费用为1.
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
init();
S=0,T=1300;
build();
printf("%d\n",cost());
}
return 0;
}