HDU 1532 Drainage Ditches 最大流裸題：Edmonds-Karp 實現

題目模型

有向圖，源點 1（池塘），匯點 M（溪流），N 條邊（溝渠）帶容量。求最大流量。N,M ≤ 200，容量 ≤ 1e7，多測試用例。

算法選擇：Edmonds-Karp (BFS 尋增廣路)

• 複雜度 O(V E²) ≈ 200 × 200² = 8e6，極快；
• 實現簡單，無需當前弧優化。

核心代碼

const int MAXN = 205;
const int INF = 1e9;
int cap[MAXN][MAXN], flow[MAXN][MAXN];
int n, m;

int maxflow(int s, int t) {
    memset(flow, 0, sizeof flow);
    int total = 0;
    while (true) {
        vector pre(n+1, -1), a(n+1, 0);
        queue q; q.push(s); a[s] = INF;
        while (!q.empty() && !a[t]) {
            int u = q.front(); q.pop();
            for (int v = 1; v <= n; ++v) if (!a[v] && cap[u][v] > flow[u][v]) {
                pre[v] = u;
                a[v] = min(a[u], cap[u][v] - flow[u][v]);
                q.push(v);
            }
        }
        if (!a[t]) break;
        for (int v = t; v != s; v = pre[v]) {
            flow[pre[v]][v] += a[t];
            flow[v][pre[v]] -= a[t];
        }
        total += a[t];
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    while (cin >> n >> m) {
        memset(cap, 0, sizeof cap);
        for (int i = 0; i < n; ++i) {
            int u, v, c; cin >> u >> v >> c;
            cap[u][v] += c; // 可能有重邊
        }
        cout << maxflow(1, m) << '\n';
    }
    return 0;
}

關鍵點

• 重邊容量累加 cap[u][v] += c；
• 反向邊流量為負，殘量網絡隱式構建；
• 輸入直到 EOF，無 0 0 終止標記（注意題目描述與樣例一致）。

樣例驗證

輸入:
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
輸出: 50

路徑 1-2-3-4 (30) + 1-4 (20) = 50。