POJ 2195 Going Home(费用流)

POJ 2195 Going Home(费用流)

http://poj.org/problem?id=2195

题意:

给定一个N*M的地图，地图上有若干个man和house，且man与house的数量一致。man每移动一格需花费$1（即单位费用=单位距离），一间house只能入住一个man。现在要求所有的man都入住house，求最小费用。

分析:

之前用二分图最大权匹配做过一次这个题目:

http://blog.csdn.net/u013480600/article/details/38735423

现在用费用流再做一次,建图如下:

源点s编号0, 人编号1到n, 房子编号n+1到n+n, 汇点编号t.

源点s到每个人i有边(s, i, 1,0)

每个人i到每个房子j有边(i, j, 1, i人到j房的开销)

每个房子j到汇点t有边(j, t, 1, 0)

最终我们求出的最小费用就是所求.

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
#define INF 1e9
using namespace std;
const int maxn=200+5;

struct Edge
{
    int from,to,cap,flow,cost;
    Edge(){}
    Edge(int f,int t,int c,int fl,int co):from(f),to(t),cap(c),flow(fl),cost(co){}
};

struct MCMF
{
    int n,m,s,t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool inq[maxn];
    int d[maxn];
    int p[maxn];
    int a[maxn];

    void init(int n,int s,int t)
    {
        this->n=n, this->s=s, this->t=t;
        edges.clear();
        for(int i=0;i<n;++i) G[i].clear();
    }

    void AddEdge(int from,int to,int cap,int cost)
    {
        edges.push_back(Edge(from,to,cap,0,cost));
        edges.push_back(Edge(to,from,0,0,-cost));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BellmanFord(int &flow,int &cost)
    {
        for(int i=0;i<n;++i) d[i]=INF;
        queue<int> Q;
        memset(inq,0,sizeof(inq));
        d[s]=0, Q.push(s), a[s]=INF, p[s]=0, inq[s]=true;
        while(!Q.empty())
        {
            int u=Q.front(); Q.pop();
            inq[u]=false;
            for(int i=0;i<G[u].size();++i)
            {
                Edge &e=edges[G[u][i]];
                if(e.cap>e.flow && d[e.to]>d[u]+e.cost)
                {
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=G[u][i];
                    a[e.to]=min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){ Q.push(e.to); inq[e.to]=true; }
                }
            }
        }
        if(d[t]==INF) return false;
        flow +=a[t];
        cost +=a[t]*d[t];
        int u=t;
        while(u!=s)
        {
            edges[p[u]].flow +=a[t];
            edges[p[u]^1].flow -=a[t];
            u=edges[p[u]].from;
        }
        return true;
    }

    int solve()
    {
        int flow=0,cost=0;
        while(BellmanFord(flow,cost));
        return cost;
    }
}MM;

struct Node
{
    int x,y;
    Node(){}
    Node(int x,int y):x(x),y(y){}
    int get_dist(Node& b)
    {
        return abs(x-b.x)+abs(y-b.y);
    }
}node1[maxn],node2[maxn];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2 && n)
    {
        int num1=0,num2=0;//记录人数和房子数
        for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            char ch;
            scanf(" %c",&ch);
            if(ch=='m') node1[num1++]=Node(i,j);
            else if(ch=='H') node2[num2++]=Node(i,j);
        }

        int src=0,dst=num1*2+1;
        MM.init(num1*2+2,src,dst);
        for(int i=1;i<=num1;++i)
        {
            MM.AddEdge(src,i,1,0);
            MM.AddEdge(num1+i,dst,1,0);
            for(int j=1;j<=num1;++j)
            {
                MM.AddEdge(i,num1+j,1,node1[i-1].get_dist(node2[j-1]));
            }
        }
        printf("%d\n",MM.solve());
    }
    return 0;
}