poj_2195Going Home(最小费用最大流)

标签： 最小费用最大流

---

题目链接

题意：

有n*m的矩阵，H表示这个点是一个房子，m表示这个点是一个人，现在每一个人需要走入一个房间，已经知道的是认得数目和房子的个数一定是相同的，现在问这些人都回到一个房间所走的总的步数最小

题解：

这个题是一个很典型的最小费用最大流的模板题，建图也很容易想到，就是增加一个新的源点和汇点，从源点到每一个人建一条流量为1，费用为0的边，每个房子到汇点也建立一条流量为1，费用为0的边，每个人都与所有的房子建立费用为两者距离，流量为1的边，然后求一遍最小费用最大流即可。

算法介绍：

我们知道最大流是通过每次寻找增广路来求解的，而现在要在保证最大流的情况下让费用最小，那就可以每次寻找增广路的时候用SPFA找满足增广路条件，即可增广，的情况下的最短路，然后对这条路径进行增广，然后更新残留网络，然后再找最短路，直到找不到了为止。

这种题理解了实现的原理，然后直接套用模板即可

最小费用最大流模板

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <algorithm>

#include <queue>

#define V 60100

#define E 1000100

#define inf 99999999

using namespace std;

int vis[V];

int dist[V];

int pre[V];

int Abs(int a){

    if(a<0) return 0-a;

    else return a;

}

struct Edge{

    int u,v,c,cost,next;

}edge[E];

int head[V],cnt;

void init(){

    cnt=0;

    memset(head,-1,sizeof(head));

}

void addedge(int u,int v,int c,int cost)

{

    edge[cnt].u=u;

    edge[cnt].v=v;

    edge[cnt].cost=cost;

    edge[cnt].c=c;

    edge[cnt].next=head[u];

    head[u]=cnt++;

    edge[cnt].u=v;

    edge[cnt].v=u;

    edge[cnt].cost=-cost;

    edge[cnt].c=0;

    edge[cnt].next=head[v];

    head[v]=cnt++;

}

bool spfa(int begin,int end){

    int u,v;

    queue<int> q;

    for(int i=0;i<=end+2;i++){

        pre[i]=-1;

        vis[i]=0;

        dist[i]=inf;

    }

    vis[begin]=1;

    dist[begin]=0;

    q.push(begin);

    while(!q.empty()){

        u=q.front();

        q.pop();

        vis[u]=0;

        for(int i=head[u];i!=-1;i=edge[i].next){

            if(edge[i].c>0){

                v=edge[i].v;

                if(dist[v]>dist[u]+edge[i].cost){

                    dist[v]=dist[u]+edge[i].cost;

                    pre[v]=i;

                    if(!vis[v]){

                        vis[v]=true;

                        q.push(v);

                    }

                }

            }

        }

    }

    return dist[end]!=inf;

}

int MCMF(int begin,int end){

    int ans=0,flow;

    int flow_sum=0;

    while(spfa(begin,end)){

        flow=inf;

        for(int i=pre[end];i!=-1;i=pre[edge[i].u])

            if(edge[i].c<flow)

                flow=flow,edge[i].c;

        for(int i=pre[end];i!=-1;i=pre[edge[i].u]){

            edge[i].c-=flow;

            edge[i^1].c+=flow;

        }

        ans+=dist[end];

        flow_sum += flow;

    }

    //cout << flow_sum << endl;

    return ans;

}

下面是这个题的ac代码

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <algorithm>

#include <queue>

#define V 60100

#define E 1000100

#define inf 99999999

using namespace std;

int vis[V];

int dist[V];

int pre[V];

int Abs(int a){

    if(a<0) return 0-a;

    else return a;

}

struct Edge{

    int u,v,c,cost,next;

}edge[E];

int head[V],cnt;

void init(){

    cnt=0;

    memset(head,-1,sizeof(head));

}

void addedge(int u,int v,int c,int cost)

{

    edge[cnt].u=u;

    edge[cnt].v=v;

    edge[cnt].cost=cost;

    edge[cnt].c=c;

    edge[cnt].next=head[u];

    head[u]=cnt++;

    edge[cnt].u=v;

    edge[cnt].v=u;

    edge[cnt].cost=-cost;

    edge[cnt].c=0;

    edge[cnt].next=head[v];

    head[v]=cnt++;

}

bool spfa(int begin,int end){

    int u,v;

    queue<int> q;

    for(int i=0;i<=end+2;i++){

        pre[i]=-1;

        vis[i]=0;

        dist[i]=inf;

    }

    vis[begin]=1;

    dist[begin]=0;

    q.push(begin);

    while(!q.empty()){

        u=q.front();

        q.pop();

        vis[u]=0;

        for(int i=head[u];i!=-1;i=edge[i].next){

            if(edge[i].c>0){

                v=edge[i].v;

                if(dist[v]>dist[u]+edge[i].cost){

                    dist[v]=dist[u]+edge[i].cost;

                    pre[v]=i;

                    if(!vis[v]){

                        vis[v]=true;

                        q.push(v);

                    }

                }

            }

        }

    }

    return dist[end]!=inf;

}

int MCMF(int begin,int end){

    int ans=0,flow;

    int flow_sum=0;

    while(spfa(begin,end)){

        flow=inf;

        for(int i=pre[end];i!=-1;i=pre[edge[i].u])

            if(edge[i].c<flow)

                flow=flow,edge[i].c;

        for(int i=pre[end];i!=-1;i=pre[edge[i].u]){

            edge[i].c-=flow;

            edge[i^1].c+=flow;

        }

        ans+=dist[end];

        flow_sum += flow;

    }

    //cout << flow_sum << endl;

    return ans;

}

char mp[202][202];

int HH[V];

int HL[V];

int MH[V];

int ML[V];

int S,T;

int cm,ch;

int main()

{

    int n,m;

    while(~scanf("%d%d",&n,&m),n+m)

    {

        init();

        getchar();

        for(int i = 0; i < n; i++){

            gets(mp[i]);

        }

        cm = ch = 1;

        for(int i = 0; i < n; i++){

            for(int j = 0; j < m; j++){

                //printf("%c ",mp[i][j]);

                if(mp[i][j]=='H'){

                    HH[ch] = i;

                    HL[ch++] = j;

                }

                else if(mp[i][j]=='m'){

                    MH[cm] = i;

                    ML[cm++] = j;

                }

            }

        }

        cm--;

        ch--;

        S = 0;

        T = cm+ch+1;

        for(int i = 1; i <= cm; i++){

            addedge(S,i,1,0);

        }

        for(int i = 1; i <= ch; i++){

            addedge(cm+i,T,1,0);

        }

        for(int i = 1; i <= cm; i++){

            for(int j = 1; j <= ch; j++){

                int tm = Abs(HH[j]-MH[i])+Abs(HL[j]-ML[i]);

                //printf("(%d,%d)-(%d,%d),tm = %d\n",HH[j],HL[j],MH[i],ML[i],tm);

                addedge(i,cm+j,1,tm);

                //printf("(%d,%d)",i,j);

            }

        }

        int ans = MCMF(S,T);

        printf("%d\n",ans);

    }

    return 0;

}