学步园

题目链接:   poj 2195

题目大意:   给出NxM的地图，'.'表示可以走的，'H'表示家，'m'表示人，H和m的数目相同

                  求把所有人移动到H的最小步数

解题思路:   建立超级源点，分别连接每个m，容量为1，费用0

                  建立超级汇点，分别把每个H连接到汇点，容量为1，费用为0

                  再把每个m分别指向H，容量为1，费用为该m到H的横纵左边之差的绝对值的和，|X1-X2|+|Y1-Y2|

                  PS: 最小费用最大流与一般增广路的区别在于，每次寻找的增广路都是代价最小的路径

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 206
#define INF 0x3f3f3f3f
#define Min(a,b) ((a<b)?a:b)
int S,E,M,H,Index,dist[MAX],pre[MAX],visit[MAX],Map[MAX][MAX],listb[1000000];
int Value[MAX][MAX],path[MAX];
char ch[MAX][MAX];
struct node{
    int x,y;
}Num1[MAX*MAX],Num2[MAX*MAX];

struct snode{
    int c,w,to,next;
}Edge[200*200*2];

int Fabs(int x)
{
    return (x<0)?-x:x;
}

void Add_edge(int a,int b,int c,int d)
{
    Value[a][b]=d;     //标记改变的费用
    if(c>=0)            //构建残留网络
        Map[a][b]=c;
    Edge[Index].to=b,Edge[Index].c=c;
    Edge[Index].w=d,Edge[Index].next=pre[a];
    pre[a]=Index++;
}

bool BFS()
{
    int i,e,s,v,vv;
    s=e=0;
    memset(path,-1,sizeof(path));
    memset(dist,INF,sizeof(dist));
    memset(visit,0,sizeof(visit));
    listb[s++]=S;visit[S]=1; dist[S]=0;
    while(s!=e)
    {
        v=listb[e++];
        visit[v]=0;
        for(i=pre[v];i!=-1;i=Edge[i].next)
        {
            vv=Edge[i].to;
            if(Map[v][vv]>0&&(dist[vv]==INF||dist[vv]>dist[v]+Edge[i].w))
            {     //最短路寻找代价最小的增广路
                path[vv]=v;
                dist[vv]=dist[v]+Edge[i].w;
                if(!visit[vv])      //防止重复入队列
                {
                    visit[vv]=1;
                    listb[s++]=vv;
                }
            }
        }
    }
    if(dist[E]==INF)  //不能到达汇点，增广结束
        return false;
    return true;
}

int Find()
{
    int sum=0,i,MIN=INF;
    for(i=E;i!=-1;i=path[i])     //找短板
    {
        if(path[i]!=-1)
            MIN=Min(MIN,Map[path[i]][i]);
    }
    for(i=E;i!=-1;i=path[i])     //更新增广路
    {
        if(path[i]!=-1)
        {
            Map[path[i]][i]-=MIN;
            Map[i][path[i]]+=MIN;
            sum=sum+Value[path[i]][i];  //代价是每条边的权值，所以不需要乘与
        }
    }
    return sum;
}

int Solve()
{
    int sum=0;
    while(BFS())
        sum+=Find();
    return sum;
}

int main()
{
    int i,n,j,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Index=0;
        if(n==0&&m==0)
            break;
        memset(pre,-1,sizeof(pre));
        memset(Map,0,sizeof(Map));
        memset(Value,0,sizeof(Value));
        M=H=0;
        for(i=1;i<=n;i++)
        {
            scanf("%s",ch[i]+1);
            for(j=1;j<=m;j++)
            {
                if(ch[i][j]=='H')
                {
                    H++;
                    Num1[H].x=i,Num1[H].y=j;
                }
                else if(ch[i][j]=='m')
                {
                    M++;
                    Num2[M].x=i,Num2[M].y=j;
                }
            }
        }
        int a,b,c,d,i1;
        S=0,E=H+M+1;
        for(i=1;i<=M;i++)      //左边
        {
            a=S,b=i,c=1,d=0;
            Add_edge(a,b,c,d);
            Add_edge(b,a,-c,-d);
        }
        for(i=M+1,j=1;j<=H;j++,i++)  //右边
        {
            a=i,b=E,c=1,d=0;
            Add_edge(a,b,c,d);
            Add_edge(b,a,-c,-d);
        }
        for(i=1;i<=M;i++)    //中间
        {
            for(j=M+1,i1=1;j<=H+M;j++,i1++)
            {
                a=i,b=j,c=1;
                d=Fabs(Num1[i].x-Num2[i1].x)+Fabs(Num1[i].y-Num2[i1].y);
                Add_edge(a,b,c,d);
                Add_edge(b,a,-c,-d);
            }
        }
        printf("%d\n",Solve());
    }
    return 0;
}