hdu1553Going Home

106 阅读 0 评论 70 点赞

我是靠谱客的博主彪壮枫叶，最近开发中收集的这篇文章主要介绍hdu1553Going Home，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

点击打开链接

给出一个图,m代表人,H表示房子,人走到房子,问所有人都进到房子时最小的花费,

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <climits>  //INT_MAX
using namespace std;
typedef long long ll;
const int inf=INT_MAX>>1;
const int M=2000;
char mp[M][M];
int pre[M],dis[M],vis[M],H[M],n,m,S,T,cnt;
struct edge
{
    int u,v,c,w,next;
}a[500000];
struct node
{
    int x,y;
}X[M],Y[M];
void init()
{
    memset(H,-1,sizeof(H));
    memset(pre,0,sizeof(pre));
    cnt=0;
}
void add(int u,int v,int c,int w)
{
    a[cnt].u=u; a[cnt].v=v; a[cnt].c=c; a[cnt].w=w; a[cnt].next=H[u]; H[u]=cnt++;
}
void build(int u,int v,int c,int w)
{
    add(u,v,c,w);
    add(v,u,0,-w);
}
int spfa(int s,int t)
{
    int i,j,k;
    for(i=0;i<=T+1;i++)
        dis[i]=inf;
    memset(vis,0,sizeof(vis));
    //memset(pre,-1,sizeof pre);//这搞错,wr到恶心
    dis[s]=0;
    vis[s]=1;
    queue<int>Q;
    Q.push(s);
    int u,v,w;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        vis[u]=0;//?
        for(j=H[u];~j;j=a[j].next){
            v=a[j].v;
            w=a[j].w;
            if(a[j].c &&dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                pre[v]=j;//纪录前边
                if(!vis[v]){
                    Q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    if(!dis[t])
        return 0;
    int delta=inf;
    v=t;
    while(v!=s){///找到可以允许的最大流
        i=pre[v];//cout<<i<<"    ";system("PAUSE");
        delta=min(delta,a[i].c);
        v=a[i].u;
    }
    v=t;
    while(v!=s){///将这条路径上的容量-割,
        i=pre[v];
        a[i].c-=delta;
        a[i^1].c=delta;
        v=a[i].u;
    }
    return dis[t]*delta;
}
int MCMF(int s,int t)
{
    int ans=0,delta=0;
    while(delta=spfa(s,t)){///不停的找最短路的最大流
        ans+=delta;
       // cout<<delta<<endl;system("PAUSE");
    }
    return ans;
}
int main()
{
    int n,m,u,v,c,w,i,j,k;
    while(scanf("%d%d",&n,&m),n||m){
        init();
        int ch=0,cm=0;
        for(i=0;i<n;i++){
            scanf("%s",mp[i]);
            for(j=0;j<m;j++){
                if(mp[i][j]=='H'){
                        X[ch].x=i;
                        X[ch++].y=j;
                }
                else if(mp[i][j]=='m'){
                    Y[cm].x=i;
                    Y[cm++].y=j;
                }
            }
        }
        S=0;
        T=2*ch+1;
        for(i=0;i<cm;i++){
            build(0,i+1,1,0);///源点到人最开始的位置建边,c=1,w=0
            for(j=0;j<ch;j++){
                int tmp=fabs(X[i].x-Y[j].x)+fabs(X[i].y-Y[j].y);///费用
                build(i+1,j+1+ch,1,tmp);///人到房子建边,c=1,w=tmp
            }
            build(i+1+ch,T,1,0);///从房子到汇点建边,c=1,w=0
        }
        ///最后要求的就是从源点到汇点的最小花费最大流
        int ans=MCMF(S,T);
        printf("%dn",ans);
    }
    return 0;
}