题意：
人回家，一步一块钱，有x个人，y个房子，求能回家的最大人数且使之费用最小
解析：
就是。。。。套模板，，，，
建图(⊙﹏⊙)。。。要仔细观察呐
对于人拆不拆都可以 都能过，，，，这里贴上拆开的代码。。。。
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn = 100100, INF = 0x7fffffff; typedef long long LL; int head[maxn], d[maxn], cur[maxn], vis[maxn], p[maxn], f[maxn]; int n, m, s, t; int cnt, flow, value; struct edge{ int x, y; }; struct node{ int u, v, c, w, next; }Node[maxn*4]; void add_(int u, int v, int c, int w) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].c = c; Node[cnt].w = w; Node[cnt].next = head[u]; head[u] = cnt++; } void add(int u, int v, int c, int w) { add_(u, v, c, w); add_(v, u, 0, -w); } int spfa() { queue<int> Q; for(int i=0; i<maxn; i++) d[i] = INF; d[s] = 0; mem(vis, 0); mem(p, -1); Q.push(s); vis[s] = 1; p[s] = 0; f[s] = INF; while(!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for(int i=head[u]; i!=-1; i=Node[i].next) { node e = Node[i]; if(d[e.v] > d[e.u] + e.w && e.c > 0) { d[e.v] = d[e.u] + e.w; p[e.v] = i; f[e.v] = min(f[u], e.c); if(!vis[e.v]) { Q.push(e.v); vis[e.v] = 1; } } } } if(p[t] == -1) return 0; flow += f[t], value += d[t]; for(int i=t; i!=s; i=Node[p[i]].u) { Node[p[i]].c -= f[t]; Node[p[i]^1].c += f[t]; } return 1; } void max_flow() { while(spfa()); printf("%d ",value); } int main() { while(~scanf("%d%d",&n,&m) && n+m) { s = 0; t = 3*n*m+100; edge hou[maxn], men[maxn]; flow = 0; value = 0; cnt = 0; mem(head, -1); char str[110][110]; int cnt1 = 1, cnt2 = 1; for(int i=0; i<n; i++) { scanf("%s",str[i]); for(int j=0; j<m; j++) { if(str[i][j] == 'H') { hou[cnt1].x = i; hou[cnt1].y = j; add(cnt1, t, 1, 0); cnt1++; } if(str[i][j] == 'm') { men[cnt2].x = i; men[cnt2].y = j; add(n*m+cnt2, 2*n*m + cnt2, 1, 0); add(s, n*m+cnt2, 1, 0); cnt2++; } } } for(int i=1; i<cnt2; i++) for(int j=1; j<cnt1; j++) { add(2*n*m+i, j, 1, abs(men[i].x - hou[j].x) + abs(men[i].y - hou[j].y)); } max_flow(); } return 0; }