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

POJ 1459 Power Network：多源多匯最大流（Edmonds-Karp 算法）

編輯：關於C++

POJ 1459 Power Network 完整解析

電力網絡：發電站（源）、用戶（匯）、調度節點、輸電線（有容量上限）。多源多匯，求最大消耗功率（最大流）。N ≤ 100，邊數 ≤ N²。

建模：超級源點 + 超級匯點

原圖節點編號 0~N-1，新增超級源 S = N、超級匯 T = N+1
S 向每個發電站連邊，容量 = 最大發電量
每個用戶向 T 連邊，容量 = 最大用電量
輸電線雙向？題目說「從 u 到 v 最多一條」，有向邊，容量 = 最大傳輸量

Edmonds-Karp 算法（BFS 尋找增廣路）

int max_flow(int s, int t) {
    int flow = 0;
    while (true) {
        fill(level, level + V, -1);
        queue q; q.push(s); level[s] = 0;
        // BFS 建立層次圖
        while (!q.empty()) { ... }
        if (level[t] < 0) break;
        
        fill(iter, iter + V, 0);
        int f;
        while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
    return flow;
}

本題規模小，Dinic 或 Edmonds-Karp 均可。下方為 EK 實作。

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

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

int cap[MAXN][MAXN], flow[MAXN][MAXN];
int parent[MAXN], min_cap[MAXN];
int n, np, nc, m;

int edmonds_karp(int s, int t) {
    int total = 0;
    while (true) {
        fill(min_cap, min_cap + n + 2, 0);
        min_cap[s] = INF;
        queue q; q.push(s);
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v = 0; v <= n + 1; v++) {
                if (!min_cap[v] && cap[u][v] > flow[u][v]) {
                    min_cap[v] = min(min_cap[u], cap[u][v] - flow[u][v]);
                    parent[v] = u;
                    q.push(v);
                }
            }
        }
        if (!min_cap[t]) break;
        
        for (int v = t; v != s; v = parent[v]) {
            flow[parent[v]][v] += min_cap[t];
            flow[v][parent[v]] -= min_cap[t];
        }
        total += min_cap[t];
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    while (cin >> n >> np >> nc >> m) {
        memset(cap, 0, sizeof(cap));
        memset(flow, 0, sizeof(flow));
        
        for (int i = 0; i < m; i++) {
            int u, v, w;
            scanf(" (%d,%d)%d", &u, &v, &w);
            cap[u+1][v+1] += w; // 節點編號 +1 避開超級源匯
        }
        
        for (int i = 0; i < np; i++) {
            int u, w;
            scanf(" (%d)%d", &u, &w);
            cap[0][u+1] += w; // 超級源 0
        }
        
        for (int i = 0; i < nc; i++) {
            int u, w;
            scanf(" (%d)%d", &u, &w);
            cap[u+1][n+1] += w; // 超級匯 n+1
        }
        
        cout << edmonds_karp(0, n+1) << '\n';
    }
    return 0;
}