POJ 2195：Going Home（最小费用最大流）

时间：2021-07-14 18:25:42

http://poj.org/problem?id=2195

题意：有一个地图里面有N个人和N个家，每走一格的花费是1，问让这N个人分别到这N个家的最小花费是多少。

思路：通过这个题目学了最小费用最大流。最小费用最大流是保证在流量最大的情况下，使得费用最小。

建图是把S->人->家->T这些边弄上形成一个网络，边的容量是1（因为一个人只能和一个家匹配），边的费用是曼哈顿距离，反向边的费用是-cost。

算法的思想大概是通过SPFA找增广路径，并且找的时候费用是可以松弛的。当找到这样一条增广路就进行更新。注意这里的费用是单位流量的费用。反向边权为-cost是因为悔棋的时候费用要增加cost。

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <vector>

 #include <algorithm>

 using namespace std;

 #define N 205

 #define INF 0x3f3f3f3f

 struct node {

     int x, y;

     node () {}

     node (int x, int y) : x(x), y(y) {}

 };

 struct Edge {

     int cap, u, v, cost;

     Edge() {}

     Edge(int u, int v, int cap, int cost) : u(u), v(v), cap(cap), cost(cost) {}

 }edge[N*N];

 vector<node> p, h;

 vector<int> G[N];

 int tot, dis[N], inq[N], pre[N], S, T;

 void AddEdge(int u, int v, int cap, int cost) {

     edge[tot] = Edge(u, v, cap, cost);

     G[u].push_back(tot++);

     edge[tot] = Edge(v, u, , -cost); // 表示反向增广(悔棋)的时候费用增加cost

     G[v].push_back(tot++);

 }

 int CalDis(int x1, int y1, int x2, int y2) {

     return abs(x1 - x2) + abs(y1 - y2);

 }

 bool SPFA() {

     memset(inq, , sizeof(inq));

     memset(dis, INF, sizeof(dis));

     queue<int> que; que.push(S);

     dis[S] = ; inq[S] = ;

     while(!que.empty()) {

         int u = que.front(); que.pop(); inq[u] = ;

         for(int i = ; i < G[u].size(); i++) {

             Edge &e = edge[G[u][i]];

             if(e.cap >  && dis[e.v] > e.cost + dis[u]) {

             // 当可以增广并且费用可以松弛的时候

                 dis[e.v] = e.cost + dis[u];

                 pre[e.v] = G[u][i]; // 记录路径

                 if(inq[e.v]) continue;

                 que.push(e.v); inq[e.v] = ;

             }

         }

     }

     return dis[T] < INF; // 返回是否有增广路径

 }

 void MFMC(int &mincost, int &maxflow) {

     int ans = , flow = INF, p;

     // 从汇点沿着此次增广的路径往回走,当找到源点的时候退出

     for(int u = T; u; u = edge[p].u) {

         p = pre[u]; // 找增广的流量

         if(edge[p].cap < flow) flow = edge[p].cap;

     }

     for(int u = T; u; u = edge[p].u) {

         p = pre[u];

         edge[p].cap -= flow; // 更新每条边的流量

         edge[p^].cap += flow;

         ans += flow * edge[p].cost; // 费用 = 单位费用 * 流量

     }

     mincost += ans, maxflow += flow;

 }

 int main() {

     int n, m;

     char s[];

     while(scanf("%d%d", &n, &m), n + m) {

         p.clear(); h.clear();

         for(int i = ; i < n; i++) {

             scanf("%s", s);

             for(int j = ; j < m; j++) {

                 if(s[j] == 'H') h.push_back(node(i, j));

                 if(s[j] == 'm') p.push_back(node(i, j));

             }

         }

         tot = ; int sz1 = p.size(), sz2 = h.size();

         S = , T = sz1 + sz2 + ;

         for(int i = ; i <= T; i++) G[i].clear();

         for(int i = ; i < sz1; i++) // S到man

             AddEdge(S, i + , , );

         for(int i = ; i < sz2; i++) // house到T

             AddEdge(i +  + sz1, T, , );

         for(int i = ; i < sz1; i++) {

             for(int j = ; j < sz2; j++) {

                 int c = CalDis(p[i].x, p[i].y, h[j].x, h[j].y);

                 AddEdge(i + , j +  + sz1, , c);

             }

         }

         int mincost = , maxflow = ;

         while(SPFA()) MFMC(mincost, maxflow);

         printf("%d\n", mincost);

     }

     return ;

 }

相关文章