本文主要是介绍poj - 2195 - Going Home（最小费用最大流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n个人，n个房子，一个人每走一步（可上、下、左、右取一个方向）花费1美元，问让这n个人走到n个房子里最少需要多少美元(n <= 100)。
题目链接：http://poj.org/problem?id=2195
——>>在学最小费用最大流，找模版题找到了这道。
建图：1到n为人的编号，n+1到2*n为房子的编号，另加上源点0和汇点2*n+1；
源点到每个人各建立一条容量为1的流，费用为0；
每个人到每个房子各建立一条容量为1的流，费用按题意计算；（注意：反向费用！！！）
每个房子到汇点建立一条容量为1的流，费用为0。
当满足最大流时，一定是源点发出n，每个人接收1并发出1到一个房子，n个房子各发出1汇成n到汇点，所以，真是最小费用最大流的模版题。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <algorithm>using namespace std;const int maxn = 2 * (100 + 10);
const int INF = 0x3f3f3f3f;struct node{ //结点类型int x;int y;
}m[maxn], h[maxn];int N, M, n, t, mid, hid, cost[maxn][maxn], cap[maxn][maxn], flow[maxn][maxn], p[maxn];
vector<node> man, house;void init(){ //初始化mid = 0;hid = 0;memset(cost, 0, sizeof(cost));memset(cap, 0, sizeof(cap));
}void build(){ //建图n = mid;t = mid + hid + 1;int i, j;for(i = 1; i <= n; i++){for(j = 1; j <= n; j++){cap[i][j+n] = 1;cost[i][j+n] = abs(m[i].x - h[j].x) + abs(m[i].y - h[j].y);cost[j+n][i] = -cost[i][j+n]; //注意这里加上回流！！！}}for(i = 1; i <= n; i++) cap[0][i] = 1;for(i = n+1; i < t; i++) cap[i][t] = 1;
}int solve(int s){queue<int> qu;int d[maxn];memset(flow, 0, sizeof(flow));int c = 0;for(;;){bool inq[maxn];memset(d, 0x3f, sizeof(d));d[0] = 0;memset(inq, 0, sizeof(inq));qu.push(s);while(!qu.empty()){int u = qu.front(); qu.pop();inq[u] = 0;for(int v = 0; v <= t; v++) if(cap[u][v] > flow[u][v] && d[u] + cost[u][v] < d[v]){d[v] = d[u] + cost[u][v];p[v] = u;if(!inq[v]){qu.push(v);inq[v] = 1;}}}if(d[t] == INF) break;int a = INF;for(int u = t; u != s; u = p[u]) a = min(a, cap[p[u]][u] - flow[p[u]][u]);for(int u = t; u != s; u = p[u]){flow[p[u]][u] += a;flow[u][p[u]] -= a;}c += d[t] * a;}return c;
}int main()
{int i, j;char c;while(scanf("%d%d", &N, &M) == 2){if(!N && !M) return 0;init();for(i = 0; i < N; i++){getchar();for(j = 0; j < M; j++){c = getchar();if(c == 'H') h[++hid] = (node){i, j};if(c == 'm') m[++mid] = (node){i, j};}}build();printf("%d\n", solve(0));}return 0;
}
这篇关于poj - 2195 - Going Home（最小费用最大流）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
