HDU 1532 Drainage Ditches 最大流增廣路算法詳解

問題描述

給定一個有向圖，每條邊有容量上限。求從源點（1號節點）到匯點（N號節點）的最大流量。這是經典的最大流問題，可用 Ford-Fulkerson 增廣路算法或 Edmonds-Karp 算法求解。

算法原理

Ford-Fulkerson 方法：反覆尋找殘量網路中的增廣路，沿路徑增加流量，直到不存在增廣路為止。使用 BFS 尋找最短增廣路即為 Edmonds-Karp 算法，時間複雜度 O(VE²)。

關鍵數據結構

• g[u][v].c：邊 u→v 的容量
• g[u][v].f：邊 u→v 的當前流量
• 殘量容量 = c - f（正向邊），f（反向邊）

增廣路搜索過程

1. 初始化隊列，從源點開始 BFS
2. 記錄前驅節點 p[v] 和路徑上最小殘量 a[v]
3. 到達匯點時，沿前驅回溯更新流量
4. 正向邊增加流量，反向邊減少流量

代碼實現要點

struct Edge { int c, f; } g[MAXN][MAXN];
int p[MAXN], a[MAXN], flag[MAXN];

void ford_fulkerson() {
    while (true) {
        memset(flag, -1, sizeof(flag));
        memset(p, -1, sizeof(p));
        memset(a, 0, sizeof(a));
        a[0] = INF; p[0] = 0; flag[0] = 0;
        
        queue q; q.push(0);
        while (!q.empty() && flag[n-1] == -1) {
            int u = q.front(); q.pop();
            for (int i = 0; i < n; ++i) {
                // 正向邊有殘量
                if (g[u][i].c > g[u][i].f && flag[i] == -1) {
                    flag[i] = 0; p[i] = u;
                    a[i] = min(a[u], g[u][i].c - g[u][i].f);
                    q.push(i);
                }
                // 反向邊有流量可回退
                else if (g[i][u].f > 0 && flag[i] == -1) {
                    flag[i] = 0; p[i] = -u;
                    a[i] = min(a[u], g[i][u].f);
                    q.push(i);
                }
            }
        }
        if (a[n-1] == 0) break; // 無增廣路
        
        // 更新流量
        for (int u = n-1, v = abs(p[u]); u != 0; u = v, v = abs(p[v])) {
            if (p[u] > 0) g[p[u]][u].f += a[n-1];
            else g[u][-p[u]].f -= a[n-1];
        }
        maxflow += a[n-1];
    }
}

複雜度與優化

Edmonds-Karp 保證 O(VE²) 時間。對於稀疏圖，建議使用鄰接表 + Dinic 算法（O(V²)），實際運行更快。