POJ 1459 Power Network - 多源多匯最大流標準模板題

問題描述

電力網絡包含發電站、用戶、調度節點。發電站有最大發電量 p_max，用戶有最大用電量 c_max，輸電線有最大傳輸量 l_max。求網絡最大供電量（最大流）。

n ≤ 100 節點，np 發電站，nc 用戶，m ≤ n² 輸電線。

建模：超級源匯點轉單源單匯

1. 原圖節點 0..n-1
2. 添加超級源 S = n，向每個發電站連邊，容量 = p_max
3. 添加超級匯 T = n+1，每個用戶向其連邊，容量 = c_max
4. 輸電線按輸入連邊，容量 = l_max
5. 求 S → T 最大流

Dinic 算法模板

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 105;
const int MAXM = 30000;
const int INF = 1e9;

struct Edge { int to, next, cap; } e[MAXM];
int head[MAXN], level[MAXN], cur[MAXN];
int n, np, nc, m, S, T, cnt = 1;

void addEdge(int u, int v, int cap) {
    e[++cnt] = {v, head[u], cap}; head[u] = cnt;
    e[++cnt] = {u, head[v], 0};   head[v] = cnt;
}

bool bfs() {
    memset(level, -1, sizeof(level));
    queue q; q.push(S); level[S] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (e[i].cap && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[T] != -1;
}

int dfs(int u, int flow) {
    if (u == T) return flow;
    int used = 0;
    for (int &i = cur[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (e[i].cap && level[v] == level[u] + 1) {
            int f = dfs(v, min(flow - used, e[i].cap));
            e[i].cap -= f;
            e[i^1].cap += f;
            used += f;
            if (used == flow) return used;
        }
    }
    if (!used) level[u] = -1;
    return used;
}

int dinic() {
    int flow = 0;
    while (bfs()) {
        memcpy(cur, head, sizeof(head));
        flow += dfs(S, INF);
    }
    return flow;
}

輸入解析與主程序

輸入格式特殊：(u,v)z 和 (u)z 無空格，需字符級解析。

int main() {
    while (scanf("%d%d%d%d", &n, &np, &nc, &m) == 4) {
        memset(head, 0, sizeof(head));
        cnt = 1;
        S = n; T = n + 1;
        
        char ch;
        for (int i = 0; i < m; ++i) {
            int u, v, z;
            // 讀取 (u,v)z
            do ch = getchar(); while (ch != '(');
            scanf("%d,%d)%d", &u, &v, &z);
            if (u != v) addEdge(u, v, z);
        }
        for (int i = 0; i < np; ++i) {
            int u, z;
            do ch = getchar(); while (ch != '(');
            scanf("%d)%d", &u, &z);
            addEdge(S, u, z);
        }
        for (int i = 0; i < nc; ++i) {
            int u, z;
            do ch = getchar(); while (ch != '(');
            scanf("%d)%d", &u, &z);
            addEdge(u, T, z);
        }
        printf("%d\n", dinic());
    }
    return 0;
}

關鍵技巧總結

1. 多源多匯轉單源單匯：超級源/匯點連接所有源/匯
2. 輸入解析：getchar() 跳過括號逗號，scanf 讀數字
3. BFS 隊列局部化：queue q 放在 bfs() 內部，避免多測試用例殘留
4. 當前弧優化：cur[] 數組加速 DFS，避免重複遍歷滿載邊

複雜度分析

• Dinic：O(V²E)，此處 V≤102, E≤10000+，極快
• 空間：O(E) 邊數組