# 思路:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define MX 200
#define S 0
#define T mnum+hnum+1

using namespace std;

int n,m;
typedef struct eges
{
int cap,val,u,v;
} edge;
typedef struct points
{
int x,y;
} point;
edge e[MX*MX];
point man[MX],hos[MX];
int lnum,fst[MX*MX],nxt[MX*MX];
int mnum,hnum;

point makep(int a,int b)
{
point x;
x.x=a,x.y=b;
return x;
}

void init()
{
lnum=-1;
mnum=0;
hnum=0;
memset(fst,0xff,sizeof(fst));
}

int manhat(point a,point b)
{
return abs(a.x-b.x)+abs(a.y-b.y);
}

void addeg(int nu,int nv,int cap,int val)
{
lnum++;
nxt[lnum]=fst[nu];
fst[nu]=lnum;
e[lnum].cap=cap;
e[lnum].val=val;
e[lnum].u=nu;
e[lnum].v=nv;
}

void outeg(int ee)
{
cout<<e[ee].u<<" "<<e[ee].v<<endl;
}

void input()
{
char ch;
scanf("%d%d",&n,&m);
if(n==0&&m==0)exit(0);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
ch=getchar();
while(ch!='H'&&ch!='m'&&ch!='.')ch=getchar();
if(ch=='m')man[++mnum]=makep(i,j);
else if(ch=='H')hos[++hnum]=makep(i,j);
}
}
}

void build()
{
for(int i=1; i<=mnum; i++)
{
for(int j=1; j<=hnum; j++)
{
}
}
for(int i=1; i<=mnum; i++)
{
}
for(int j=1; j<=hnum; j++)
{
}
}

int dist[MX*MX],book[MX*MX],pre[MX*MX],q[MX*MX];
int h,t,now;

bool SPFA(int *flow,int *cost)
{
memset(dist,0x3f,sizeof(dist));
memset(book,0,sizeof(book));
memset(pre,0,sizeof(pre));
memset(q,0,sizeof(q));
h=t=1;
q[h]=S;
dist[S]=0;
book[S]=1;
pre[S]=-1;
while(h>=t)
{
now=q[t];
book[q[t]]=0;
t++;
for(int i=fst[now];i!=-1;i=nxt[i])
{
if(e[i].cap>0&&dist[e[i].v]>dist[now]+e[i].val)
{
dist[e[i].v]=dist[now]+e[i].val;
pre[e[i].v]=i;
if(book[e[i].v]==0)
{
book[e[i].v]=1;
q[++h]=e[i].v;
}
}
}
}
if(dist[T]>10000)return 0;
int mxfl=99999,cstd=0;
now=pre[T];
while(now!=-1)
{
mxfl=min(mxfl,e[now].cap);
cstd+=e[now].val;
now=pre[e[now].u];
}
now=pre[T];
while(now!=-1)
{
e[now].cap-=mxfl;
e[now^1].cap+=mxfl;
now=pre[e[now].u];
}
*flow+=mxfl;
*cost+=mxfl*cstd;
return 1;
}

void minst()
{
int flow=0,cost=0;
while(SPFA(&flow,&cost));
cout<<cost<<endl;
}

int main()
{
while(1)
{
init();
input();
build();
minst();
}

return 0;
}



### 1 条评论

#### 【题解】 Going Home 最小费用最大流 HDU – 1533 | K-XZY · 2017年6月17日 11:19 下午

[…] abs 大佬太强啦！这题打了 170 行。。。蒟蒻的 3 倍啊 Orz 此题最小费用最大流模板题，也许能用二分图的最大权匹配做。 abs 的题解：http://k-xzy.cf/?p=1440 […]