题意是：有相同数量的人与房子，每一时刻人都可以花费1$的钱走一步，问让每个人到达一个屋子的最少需要的费用。
建立源点与汇点，求有源点到汇点的最小费用最大流；改了一下不需要f[][]的模板。
#include#include #include #include #include #define maxn 207using namespace std;const int inf = 999999999;struct node{ int x,y;}p[maxn],h[maxn];int c[maxn][maxn],f[maxn][maxn],w[maxn][maxn];int pre[maxn],dis[maxn];int n,m,pn,hn,s,t;char str[maxn][maxn];bool inq[maxn];int ans;int Abs(int x){ return x > 0 ? x : -x;}void spfa(){ int v; queue q; for (int i = 0; i < maxn; ++i) { dis[i] = inf; pre[i] = -1; inq[i] = false; } q.push(s); inq[s] = true; dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (v = 0; v <= t; ++v) { if (c[u][v]&& dis[v] > dis[u] + w[u][v]) { dis[v] = dis[u] + w[u][v]; pre[v] = u; if (!inq[v]) { q.push(v); inq[v] = true; } } } }}void mcmf(){ while (1) { spfa(); if (pre[t] == -1) break; int x = t,minf = inf; while (pre[x] != -1) { minf = min(minf,c[pre[x]][x]); x = pre[x]; } x = t; while (pre[x] != -1) { c[pre[x]][x] -= minf; c[x][pre[x]] += minf; ans += minf*w[pre[x]][x]; x = pre[x]; } }}int main(){ //freopen("in.txt","r",stdin); int i,j,pn,hn; while (~scanf("%d%d",&n,&m)) { if (!n && !m) break; pn = hn = 0; for (i = 0; i < n; ++i) { scanf("%s",str[i]); for (j = 0; j < m; ++j) { if (str[i][j] == 'H') { h[++hn].x = i; h[hn].y = j; } else if (str[i][j] == 'm') { p[++pn].x = i; p[pn].y = j; } } } memset(c,0,sizeof(c)); memset(f,0,sizeof(f)); memset(w,0,sizeof(w)); s = 0; t = pn + hn + 1; for (i = 1; i <= pn; ++i) c[s][i] = 1; for (i = 1; i <= hn; ++i) c[i + pn][t] = 1; for (i = 1; i <= pn; ++i) { for (j = 1; j <= hn; ++j) { c[i][j + pn] = 1; w[i][j + pn] = Abs(p[i].x - h[j].x) + Abs(p[i].y - h[j].y); w[j + pn][i] = -w[i][j + pn]; } } ans = 0; mcmf(); printf("%d\n",ans); } return 0;}