poj2195 Going Home 最小开销最大流

poj2195 Going Home 最小费用最大流

题意：给定n*m的矩阵（最大100*100）

.为空地 H为房子 m为人（题目保证 H的个数<=100 && H = m）

一个房子只能住一个人

问：让每个人回到任意一个房子使得所有人需要步数最少，问最少需要多少步。

思路：费用流，虚拟源点与人建边费用为0，一个人与所有房子建边，费用为步数，房子与汇点建边费用为0

所有边流量限制为1

/*********************************************************
  file name: poj2195.cpp
  author : kereo
  create time:  2015年01月22日 星期四 16时05分37秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=150+50;
const int MAXN=400+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=100000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,m,edge_cnt;
char mp[N][N];
int head[MAXN],inq[MAXN],d[MAXN],pre[MAXN],A[MAXN];
struct Edge{
    int v,cap,flow,cost,next;
}edge[MAXN*MAXN];
struct node{
    int x,y;
}H[N],M[N];
void init(){
    edge_cnt=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost){
    edge[edge_cnt].v=v; edge[edge_cnt].cap=cap; edge[edge_cnt].flow=0; 
    edge[edge_cnt].cost=cost; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;
    edge[edge_cnt].v=u; edge[edge_cnt].cap=0; edge[edge_cnt].flow=0;
    edge[edge_cnt].cost=-cost; edge[edge_cnt].next=head[v]; head[v]=edge_cnt++;
}
bool spfa(int st,int ed,int &flow,int &cost){
    memset(inq,0,sizeof(inq));
    for(int i=0;i<=ed;i++) d[i]=inf;
    d[st]=0; inq[st]=1; pre[st]=0; A[st]=inf; 
    queue<int>Q; 
    Q.push(st);
    while(!Q.empty()){
        int u=Q.front(); Q.pop();
        inq[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v,w=edge[i].cost;
            if(edge[i].cap>edge[i].flow && d[v]>d[u]+w){
                d[v]=d[u]+w; pre[v]=i; A[v]=min(A[u],edge[i].cap-edge[i].flow);
                if(!inq[v]){
                    Q.push(v); inq[v]=1;
                }
            }
        }
    }
    if(d[ed] == inf)
        return false;
    flow+=A[ed]; cost+=A[ed]*d[ed];
    int u=ed;
    while(u!=st){
        edge[pre[u]].flow+=A[ed];
        edge[pre[u]^1].flow-=A[ed];
        u=edge[pre[u]^1].v;
    }
    return true;
}
int solve(int st,int ed){
    int flow=0,cost=0;
    while(spfa(st,ed,flow,cost)) ;
    return cost;
}
int main(){
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d",&n,&m) && n+m){
        init();
        int cnt1=0,cnt2=0,st=0,ed=2*N;
        for(int i=0;i<n;i++){
            scanf("%s",mp[i]);
            for(int j=0;j<m;j++){
                if(mp[i][j] == 'm'){
                    M[++cnt1].x=i,M[cnt1].y=j;
                    addedge(st,cnt1,1,0);
                }
                if(mp[i][j] == 'H'){
                    H[++cnt2].x=i,H[cnt2].y=j;
                    addedge(N+cnt2,ed,1,0);
                }
            }
        }
        for(int i=1;i<=cnt1;i++){
            int u=i;
            for(int j=1;j<=cnt2;j++){
                int v=N+j;
                addedge(u,v,1,abs(M[i].x-H[j].x)+abs(M[i].y-H[j].y));
            }
        }
        printf("%d\n",solve(st,ed));
    }
	return 0;
}

poj2195 Going Home 最小开销最大流

相关推荐