题意：给你一个n*m的地图，H代表这个点有一个房子，m代表这个点是一个人，每次h走一步就花费一，问最小花费使得每个人能进入一个房间
代码：建立一个源点和汇点，每个人和源点相连，每个房子和汇点相连，每个人和每个房子相连，花费为曼哈段距离
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=1005000;
const int inf=0x3f3f3f3f;
struct node
{
int x,y;
}h[50050],man[50050];
int cntm,cnth;
struct Edge
{
int next;
int to;
int w;
int cost;
}edge[maxn];
int head[50050],dist[50050],pre[50050],path[50050];
int Start,End;
char s[1050][1050];
int cnt,x,y,w,n,m,tx,ty;
void add(int u,int v,int w,int cost)
{
// cout<<u<<" "<<v<<" "<<w<<" "<<cost<<endl;
edge[cnt].next=head[u];edge[cnt].to=v;
edge[cnt].w=w;edge[cnt].cost=cost;head[u]=cnt++;
//建回边
edge[cnt].next=head[v];edge[cnt].to=u;
edge[cnt].w=0;edge[cnt].cost=-cost;head[v]=cnt++;
}
bool spfa(int s,int t)
{
memset(pre,-1,sizeof(pre));
memset(dist,inf,sizeof(dist));
dist[s]=0;
queue<int>q;
q.push(s);
while(!q.empty())//不能有环，建图的时候也要注意
{
int u=q.front();q.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].w>0&&dist[u]+edge[i].cost<dist[v])//这条路径存在且能被优化
{
dist[v]=dist[u]+edge[i].cost;
pre[v]=u;path[v]=i;q.push(v);
}
}
}
if(pre[t]==-1)
return false;
return true;
}
int mincost(int s,int t)
{
int cost=0;int flow=0;
while(spfa(s,t))
{
int tempflow=inf;
for(int u=t;u!=s;u=pre[u])//找最小的流量
{
if(edge[path[u]].w<tempflow)
tempflow=edge[path[u]].w;
}
flow+=tempflow;//每增广一次能得到的流量；
//cost+=dist[t]*tempflow;//花费
cost+=dist[t];
for(int u=t;u!=s;u=pre[u])
{
edge[path[u]].w-=tempflow;
edge[path[u]^1].w+=tempflow;
}
}
return cost;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
memset(head,-1,sizeof(head));
cnt=cnth=cntm=0;
Start=0;End=n*m+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>s[i][j];
if(s[i][j]=='m')
{
man[++cntm].x=i;man[cntm].y=j;
}
if(s[i][j]=='H')
{
h[++cnth].x=i;h[cnth].y=j;
}
}
for(int i=1;i<=cnth;i++)
{
y=End;x=(h[i].x-1)*m+h[i].y;
add(x,y,1,0);
}
for(int i=1;i<=cntm;i++)
{
x=Start;y=(man[i].x-1)*m+man[i].y;
add(x,y,1,0);
}
for(int i=1;i<=cntm;i++)
{ x=man[i].x;y=man[i].y;
for(int j=1;j<=cnth;j++)
{
tx=h[j].x;ty=h[j].y;
w=abs(x-tx)+abs(y-ty);
add((x-1)*m+y,(tx-1)*m+ty,1,w);
}
}
int ans=mincost(Start,End);
cout<<ans<<endl;
}
}