Going Home
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 22254 | Accepted: 11236 |
Description
On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.
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.
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
There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.
Output
For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.
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
Source
大致题意：
给定一个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，是为了现在所构造的单源单汇网络流最终所求的最小费用等于原来的多源多汇网络流的最小费用。
摘自：小優YoU
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int N=5005; const int inf=0x3f3f3f3f; struct node{ int x,y; node(int x=0,int y=0):x(x),y(y){} }man[N],house[N];int cnt_man,cnt_house; struct edge{ int v,cap,cost,next; }e[N*N*4];int tot=1; int n,m,S,T,ans,head[N<<2],flow[N<<2],dis[N<<2],prev[N<<2],q[N<<4]; bool vis[N<<2];char mp[101][101]; int ABS(int x){return x>0?x:-x;} int operator -(const node &a,const node &b){ return ABS(a.x-b.x)+ABS(a.y-b.y); } void add(int x,int y,int z,int cost){ e[++tot].v=y;e[tot].cap=z;e[tot].cost=cost;e[tot].next=head[x];head[x]=tot; e[++tot].v=x;e[tot].cap=0;e[tot].cost=-cost;e[tot].next=head[y];head[y]=tot; } void mapping(){ S=0,T=cnt_man+cnt_house+1; for(int i=1;i<=cnt_man;i++){ add(S,i,1,0); for(int j=1;j<=cnt_house;j++){ add(i,cnt_man+j,1,(man[i]-house[j])); } } for(int i=1;i<=cnt_house;i++) add(cnt_man+i,T,1,0); } bool spfa(){ for(int i=S;i<=T;i++) vis[i]=0,dis[i]=inf; int h=0,t=1;dis[S]=0;q[t]=S;flow[S]=inf; while(h!=t){ int x=q[++h]; vis[x]=0; for(int i=head[x];i;i=e[i].next){ if(e[i].cap&&dis[e[i].v]>dis[x]+e[i].cost){ dis[e[i].v]=dis[x]+e[i].cost; prev[e[i].v]=i; flow[e[i].v]=min(flow[x],e[i].cap); if(!vis[e[i].v]){ vis[e[i].v]=1; q[++t]=e[i].v; } } } } return dis[T]!=inf; } void augment(){ for(int i=T;i!=S;i=e[prev[i]^1].v){ e[prev[i]].cap-=flow[T]; e[prev[i]^1].cap+=flow[T]; } ans+=dis[T]*flow[T]; } void init(){ tot=1;ans=cnt_man=cnt_house=0; memset(head,0,sizeof head); } int main(){ while(scanf("%d%d",&n,&m)==2){ if(!n&&!m) break; init(); for(int i=1;i<=n;i++) scanf("%s",mp[i]+1); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='m') man[++cnt_man]=node(i,j); if(mp[i][j]=='H') house[++cnt_house]=node(i,j); } } mapping(); while(spfa()) augment(); printf("%d ",ans); } return 0; }