首页 > 代码库 > POj 2195 Going Home（费用流）
POj 2195 Going Home（费用流）
【题目链接】 http://poj.org/problem?id=2195
【题目大意】
给出一张图，上面有n个人和n个房子，现在每个人都让其回到其中一个房子中，
每个房子只能待一个人，现在要求总的路程最短，求这个最短路程
【题解】
每个人往每个房子连一条边，流量为1，费用为路程，那么在满流情况下的费用
就是总路程的最小值。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>#include <vector>#include <utility>using namespace std;const int INF=0x3f3f3f3f;struct edge{int to,cap,cost,rev;};const int MAX_V=10000;int V,dist[MAX_V],prevv[MAX_V],preve[MAX_V];vector<edge> G[MAX_V];void add_edge(int from,int to,int cap,int cost){ G[from].push_back((edge){to,cap,cost,G[to].size()}); G[to].push_back((edge){from,0,-cost,G[from].size()-1});}int min_cost_flow(int s,int t,int f){ int res=0; while(f>0){ fill(dist,dist+V,INF); dist[s]=0; bool update=1; while(update){ update=0; for(int v=0;v<V;v++){ if(dist[v]==INF)continue; for(int i=0;i<G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&dist[e.to]>dist[v]+e.cost){ dist[e.to]=dist[v]+e.cost; prevv[e.to]=v; preve[e.to]=i; update=1; } } } } if(dist[t]==INF)return -1; int d=f; for(int v=t;v!=s;v=prevv[v]){ d=min(d,G[prevv[v]][preve[v]].cap); }f-=d; res+=d*dist[t]; for(int v=t;v!=s;v=prevv[v]){ edge &e=G[prevv[v]][preve[v]]; e.cap-=d; G[v][e.rev].cap+=d; } }return res;}void clear(){for(int i=0;i<V;i++)G[i].clear();}int N,M;int dis(pair<int,int> a,pair<int,int> b){ return abs(a.first-b.first)+abs(a.second-b.second);}void solve(){ vector<pair<int, int> >P; vector<pair<int, int> >H; for(int i=0;i<N;i++){ getchar(); for(int j=0;j<M;j++){ switch(getchar()){ case ‘m‘: P.push_back(make_pair(i,j)); break; case ‘H‘: H.push_back(make_pair(i,j)); break; } } }int size=P.size(); int s=size+size,t=s+1; V=t+1; clear(); for(int i=0;i<size;i++){ add_edge(s,i,1,0); add_edge(i+size,t,1,0); for(int j=0;j<size;j++){ add_edge(i,size+j,1,dis(P[i],H[j])); } }printf("%d\n",min_cost_flow(s,t,size));}int main(){ while(~scanf("%d%d",&N,&M),N&&M){ solve(); }return 0;}POj 2195 Going Home（费用流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。