您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 2195 最小費用流：倉鼠回家問題建模詳解

編輯：關於C++

題目大意

給定一個網格地圖，H 代表房子，m 代表人。每個人要走到一個房子，每個房子只能住一人。求所有人走到房子的總步數最小值（曼哈頓距離）。

最小費用最大流建模

經典二分圖最小權完美匹配問題，用最小費用流求解：

節點：超級源點 S、所有人節點、所有房子節點、超級匯點 T
邊：
- S → 每個人：容量 1，費用 0
- 人 → 房子：容量 1，費用 = 曼哈頓距離
- 房子 → T：容量 1，費用 0
流量：人數（即匹配數）
目標：滿流量下的最小費用

SPFA / Dijkstra + 滿費用增廣

使用SPFA（或帶勢的 Dijkstra）尋找最短增廣路徑，每次增廣 1 単位流，直到達到目標流量或無增廣路徑。

完整代碼實現

#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 10010;

struct Edge {
    int to, cap, cost, rev;
    Edge(int a, int b, int c, int d) : to(a), cap(b), cost(c), rev(d) {}
};

vector<Edge> G[MAXN];
int h[MAXN], dist[MAXN], prevv[MAXN], preve[MAXN];

void addEdge(int from, int to, int cap, int cost) {
    G[from].push_back(Edge(to, cap, cost, G[to].size()));
    G[to].push_back(Edge(from, 0, -cost, G[from].size() - 1));
}

// 最小費用流：返回滿足流量 f 的最小費用，不可行返回 -1
int minCostFlow(int s, int t, int f) {
    int res = 0;
    memset(h, 0, sizeof(h));  // 勢函數，初始為 0
    
    while (f > 0) {
        // Dijkstra 找最短路（帶勢優化負權邊）
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        fill(dist, dist + MAXN, INF);
        dist[s] = 0;
        pq.push({0, s});
        
        while (!pq.empty()) {
            auto [d, v] = pq.top(); pq.pop();
            if (dist[v] < d) continue;
            for (int i = 0; i < G[v].size(); ++i) {
                Edge &e = G[v][i];
                if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    pq.push({dist[e.to], e.to});
                }
            }
        }
        
        if (dist[t] == INF) return -1;  // 無法滿流量
        
        // 更新勢
        for (int i = 0; i < MAXN; ++i)
            if (dist[i] < INF) h[i] += dist[i];
        
        // 增廣流量
        int d = f;
        for (int v = t; v != s; v = prevv[v])
            d = min(d, G[prevv[v]][preve[v]].cap);
        
        f -= d;
        res += d * h[t];  // h[t] 是實際最短距離
        for (int v = t; v != s; v = prevv[v]) {
            Edge &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        vector<pair<int,int>> man, house;
        string line;
        for (int i = 0; i < n; ++i) {
            cin >> line;
            for (int j = 0; j < m; ++j) {
                if (line[j] == 'm') man.push_back({i, j});
                else if (line[j] == 'H') house.push_back({i, j});
            }
        }
        
        int V = man.size() + house.size() + 2;
        int S = V - 2, T = V - 1;
        for (int i = 0; i < V; ++i) G[i].clear();
        
        // 建圖
        for (int i = 0; i < man.size(); ++i) {
            addEdge(S, i, 1, 0);
            for (int j = 0; j < house.size(); ++j) {
                int cost = abs(man[i].first - house[j].first) + 
                           abs(man[i].second - house[j].second);
                addEdge(i, man.size() + j, 1, cost);
            }
        }
        for (int j = 0; j < house.size(); ++j)
            addEdge(man.size() + j, T, 1, 0);
        
        cout << minCostFlow(S, T, man.size()) << endl;
    }
    return 0;
}