题意：n个人，进n个房子，每走一格花费1美元，每个房子只能进一人，求所有人进房子的最小花费。 就是推箱子 箱子最短行走距离
这题无法用bfs做 ！
用最小花费最大流
通过EK，Dinic，ISAP算法可以得到网络流图中的最大流，一个网络流图中最大流的流量max_flow是唯一的，但是达到最大流量max_flow时每条边上的流量分配f是不唯一的。
如果给网络流图中的每条边都设置一个费用cost，表示单位流量流经该边时会导致花费cost。那么在这些流量均为max_flow的流量分配f中，存在一个流量总花费最小的最大流方案。
即 min{sum(cost(i, j)*f(i,j) | (i, j)属于方案f中的边， f(i,j)为 边(i,j)上的流量， f为某一个最大流方案}。此即为最小费用最大流。
建图：
超级源点到所有人 每个人到每个房子均算出花费 所有房子到超级汇点 所有的边均为1 花费除了人到房子均为0
可当作最小花费最大流模板：
#include <cstdio> #include <cstring> #include <queue> #include <cstdlib> #include <algorithm> #define MAXN 200+10 #define MAXM 80000+100 #define INF 0x3f3f3f3f using namespace std; struct Edge { int from, to, cap, flow, cost, next; }; Edge edge[MAXM]; int head[MAXN], edgenum; int pre[MAXN], dist[MAXN]; bool vis[MAXN]; int N, M; int cost, flow; int sink, source;//超级源点 超级汇点 void init() { edgenum = 0; memset(head, -1, sizeof(head)); } void addEdge(int u, int v, int w, int c) { Edge E1 = {u, v, w, 0, c, head[u]}; edge[edgenum] = E1; head[u] = edgenum++; Edge E2 = {v, u, 0, 0, -c, head[v]}; edge[edgenum] = E2; head[v] = edgenum++; } int dis(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2); } struct Node { int x, y; }; Node m[110], H[110];//存储字符坐标 bool SPFA(int s, int t)//寻找花销最少的路径 { queue<int> Q; memset(dist, INF, sizeof(dist)); memset(vis, false, sizeof(vis)); memset(pre, -1, sizeof(pre)); dist[s] = 0; vis[s] = true; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = false; for(int i = head[u]; i != -1; i = edge[i].next) { Edge E = edge[i]; if(dist[E.to] > dist[u] + E.cost && E.cap > E.flow)//可以松弛 且 没有满流 { dist[E.to] = dist[u] + E.cost; pre[E.to] = i;//记录前驱边 的编号 if(!vis[E.to]) { vis[E.to] = true; Q.push(E.to); } } } } return pre[t] != -1;//可达返回true } void MCMF(int s, int t) { flow = 0;//总流量 cost = 0;//总费用 while(SPFA(s, t))//每次寻找花销最小的路径 { int Min = INF; //通过反向弧 在源点到汇点的最少花费路径 找最小增广流 for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) { Edge E = edge[i]; Min = min(Min, E.cap - E.flow); } //增广 for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) { edge[i].flow += Min; edge[i^1].flow -= Min; cost += edge[i].cost * Min;//增广流的花销 } flow += Min;//流量累加 } } int main() { int m_cnt;//m字符计数器 int H_cnt;//H字符计数器 while(scanf("%d%d", &N, &M), N||M) { init(); m_cnt = H_cnt = 0; char str[110][110]; for(int i = 0; i < N; i++) { scanf("%s", str[i]); for(int j = 0; j < M; j++) { if(str[i][j] == 'm') { ++m_cnt; m[m_cnt].x = i; m[m_cnt].y = j; } if(str[i][j] == 'H') { ++H_cnt; H[H_cnt].x = i; H[H_cnt].y = j; } } } int k = m_cnt;//人数 或者 房子数 sink = 0; source = 2*k+1; for(int i = 1; i <= k; i++) { addEdge(sink, i, 1, 0); addEdge(i + k, source, 1, 0); for(int j = 1; j <= k; j++) { int d = dis(H[i].x, H[i].y, m[j].x, m[j].y); addEdge(i, j + k, 1, d); } } MCMF(sink, source); printf("%d ", cost); } return 0; }