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题解：
把每个人到每个房子的距离当成费用，添加超级源点超级汇点，所有边的流量全部为1建立模型。然后就是基础的最小费用最大流。
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 310; struct Edge{ int value,flow,to,rev; Edge(){} Edge(int a,int b,int c,int d):to(a),value(b),flow(c),rev(d){} }; vector<Edge> E[MAXN]; inline void Add(int from,int to,int flow,int value){ E[from].push_back(Edge(to,value,flow,E[to].size())); E[to].push_back(Edge(from,-value,0,E[from].size()-1)); } struct House{ int x,y;//坐标 House(int a,int b):x(a),y(b){} }; vector<House> H; struct People{ int x,y; People(int a,int b):x(a),y(b){} }; vector<People> P; bool book[MAXN];//用于SPFA中标记是否在queue中 int cost[MAXN];//存费用的最短路径 int pre[MAXN];//存前节点 int pree[MAXN];//存在前节点的vector中的下标 bool Spfa(int from,int to){ memset(book,false,sizeof book); memset(cost,INF,sizeof cost); book[from] = true; cost[from] = 0; queue<int> Q; Q.push(from); while(!Q.empty()){ int t = Q.front(); book[t] = false; Q.pop(); for(int i=0 ; i<E[t].size() ; ++i){ Edge& e = E[t][i]; if(e.flow > 0 && cost[e.to] > cost[t] + e.value){ cost[e.to] = cost[t] + e.value; pre[e.to] = t; pree[e.to] = i; if(book[e.to] == false){ Q.push(e.to); book[e.to] = true; } } } } return cost[to] != INF; } int Work(int from,int to){ int sum = 0; while(Spfa(from,to)){ int mflow = INF;//SPFA找到的最短路径的最小容量 int flag = to; while(flag != from){ mflow = min(mflow,E[pre[flag]][pree[flag]].flow); flag = pre[flag]; } flag = to; while(flag != from){ sum += E[pre[flag]][pree[flag]].value * mflow; E[pre[flag]][pree[flag]].flow -= mflow; E[flag][E[pre[flag]][pree[flag]].rev].flow += mflow; flag = pre[flag]; } } return sum; } int main(){ int N,M; char ch; while(scanf("%d %d",&N,&M) && (N || M)){ for(int i=1 ; i<=N ; ++i){ getchar(); for(int j=1 ; j<=M ; ++j){ ch = getchar(); if(ch == 'H')H.push_back(House(i,j)); else if(ch == 'm')P.push_back(People(i,j)); } } for(int i=0 ; i<P.size() ; ++i)Add(0,i+1,1,0); for(int i=0 ; i<H.size() ; ++i)Add(i+100+1,MAXN-1,1,0); for(int i=0 ; i<P.size() ; ++i){ for(int j=0 ; j<H.size() ; ++j){ int value = abs(P[i].x - H[j].x) + abs(P[i].y - H[j].y); Add(i+1,j+100+1,1,value); } } printf("%d\n",Work(0,MAXN-1));//超级源点和超级汇点为0和MAXN-1 for(int i=0 ; i<MAXN ; ++i)E[i].clear(); P.clear(); H.clear(); } return 0; }