本文主要是介绍poj 2195 going home（最小费用最大流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=2195
Description
Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point.
You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.
Input
Output
Sample Input
2 2 .m H. 5 5 HH..m ..... ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... 0 0
Sample Output
2 10 28
题目大意：
给定一个N*M的地图，地图上有若干个man和house，且man与house的数量一致。man每移动一格需花费$1（即单位费用=单位距离），一间house只能入住一个man。现在要求所有的man都入住house，求最小费用。
构图
把man作为一个顶点集合U，house作为另一个顶点集合V，把U中所有点到V中所有点连线，费用cost[u][v]为abs(△x)+abs(△y)，反向弧费用cost[v][u]= -cost[u][v]，容量cap[u][v]=1，构成一个多源多汇的二分图。
由于每一个多源多汇的网络流都必有一个与之对应的单源单汇的网络流，为了便于解题，由此构造一个超级源s和超级汇t，超级源s与U中所有点相连，费用cost[s][u]=0（这是显然的），容量cap[s][u]=1；V中所有点与超级汇t相连，费用cost[v][t]=0（这是显然的），容量cap[t][v]=1。
至于其他不连通的点，费用与容量均为0。容量为0的边，可以理解为饱和边，不再连通。而上述的所有边之所以容量初始化为1，是因为每间house只允许入住1个man。而与超级源（汇）相连的边的费用之所以为0，是为了现在所构造的单源单汇网络流最终所求的最小费用等于原来的多源多汇网络流的最小费用。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<queue>
#define INF 0x3f3f3f3f
#define N 300using namespace std;char mp[N][N];
struct node
{int x;int y;
} am[N],ah[N];
int ms,hs;
int S,T;
int c[N][N];///容量
int r[N][N];///费用
int cnt;
int pre[N],vis[N],dist[N];bool spfa(int s,int t)///求最短路，找最小费用然后曾广
{queue<int >q;while(!q.empty())q.pop();for(int i=0;i<=T;i++){pre[i]=-1;vis[i]=0;dist[i]=INF;}dist[s]=0;vis[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=1;i<=T;i++){if(c[u][i]&&dist[i]>dist[u]+r[u][i])///**对费用曾广{dist[i]=dist[u]+r[u][i];pre[i]=u;///记录路径if(!vis[i]){vis[i]=1;q.push(i);}}}}if(dist[T]!=INF)return true;///判断从原点到汇点有没有最短路（没有的话结束）else return false;
}
void mimx()
{cnt=0;while(spfa(S,T)){int mi=INF;for(int i=T;i!=0;i=pre[i])///寻找路径上可以曾广的值{mi=min(mi,c[pre[i]][i]);///这里直接对容量计算，因为容量只能为1，}for(int i=T;i!=0;i=pre[i]){c[pre[i]][i]-=mi;///流量f+a即容量-ac[i][pre[i]]+=mi;cnt+=r[pre[i]][i]*mi;///累加费用}}printf("%d\n",cnt);
}
int main()
{int n,m;while(scanf("%d%d",&n,&m)){if(n==0&&m==0)break;ms=hs=0;memset(c,0,sizeof(c));for(int i=0; i<n; i++){scanf("%s",mp[i]);for(int j=0; j<m; j++){if(mp[i][j]=='m'){am[++ms].x=i;am[ms].y=j;}else if(mp[i][j]=='H'){ah[++hs].x=i;ah[hs].y=j;}}}T=ms+hs+1;S=0;///建图for(int i=1;i<=ms;i++){c[0][i]=1;r[0][i]=0;}for(int i=1;i<=hs;i++){c[i+ms][T]=1;r[i+ms][T]=0;}for(int i=1;i<=ms;i++){for(int j=1;j<=hs;j++){c[i][j+ms]=1;r[i][j+ms]=abs(am[i].x-ah[j].x)+abs(am[i].y-ah[j].y);r[j+ms][i]=-r[i][j+ms];}}mimx();}return 0;
}
这篇关于poj 2195 going home（最小费用最大流）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
