题意:

一个地图上有很多小人要回家，每个小人都可以去任意一栋不同的房子，每个小人去一栋房子的花费为房子和人的曼哈顿距离。求最小支付多少花费可以使小人都回家？

思路:

直接套用最小费用最大流。1. 把每个小人和每个房子连边，容量为 1，费用为距离；2. 把超级源点和每个小人连边，容量为 1，费用为 0；3. 把每个房子和超级汇点连边，容量为 1，费用为 0.

#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++)
        {
            addeg(i,mnum+j,1,manhat(man[i],hos[j]));
            addeg(mnum+j,i,0,-manhat(man[i],hos[j]));
        }
    }
    for(int i=1; i<=mnum; i++)
    {
        addeg(S,i,1,0);
        addeg(i,S,0,0);
    }
    for(int j=1; j<=hnum; j++)
    {
        addeg(mnum+j,T,1,0);
        addeg(T,mnum+j,0,0);
    }
}

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;
}