POJ 1273 Drainage Ditches：Dinic 最大流算法模板題詳解

經典最大流入門題：N 個節點、M 條有向邊，每邊有容量上限，求從源點 1 到匯點 N 的最大流量。標準 Dinic 算法（分層圖 + 當前弧優化 + DFS 阻塞流）可輕松通過。

Dinic 算法核心步驟

1. BFS 分層：從源點在殘量網絡中 BFS，構建層次圖 level[v]，僅保留 level[v] = level[u] + 1 的前向邊。若匯點不可達 → 結束。
2. DFS 尋找阻塞流：在分層圖上從源點 DFS，每次沿允許邊推送流量，利用當前弧優化（ptr[v] 記錄下次嘗試的邊）避免重複探索已滿邊。
3. 重複上述直到 BFS 不能到達匯點。

關鍵數據結構

struct Edge { int to, cap, rev; }; // 反向邊索引
vector G[MAXN];
int level[MAXN], ptr[MAXN];

void addEdge(int u, int v, int cap) {
    Edge a = {v, cap, (int)G[v].size()};
    Edge b = {u, 0, (int)G[u].size()};
    G[u].push_back(a);
    G[v].push_back(b);
}

完整 Dinic 實現

bool bfs(int s, int t) {
    fill(level, level+N+1, -1);
    queue q; q.push(s); level[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto &e : G[u])
            if (e.cap > 0 && level[e.to] == -1) {
                level[e.to] = level[u] + 1;
                q.push(e.to);
            }
    }
    return level[t] != -1;
}

int dfs(int u, int t, int flow) {
    if (u == t || flow == 0) return flow;
    for (int &i = ptr[u]; i < G[u].size(); i++) {
        Edge &e = G[u][i];
        if (e.cap > 0 && level[e.to] == level[u] + 1) {
            int pushed = dfs(e.to, t, min(flow, e.cap));
            if (pushed) {
                e.cap -= pushed;
                G[e.to][e.rev].cap += pushed;
                return pushed;
            }
        }
    }
    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    while (bfs(s, t)) {
        fill(ptr, ptr+N+1, 0);
        while (int pushed = dfs(s, t, INF))
            flow += pushed;
    }
    return flow;
}

題目特殊處理

• 可能有重邊 → addEdge 直接疊加容量（或輸入時合併）。
• 節點數 ≤ 200，邊數 ≤ 20000，鄰接表 Dinic 極快。
• 原文代碼使用靜態數組 + 手動鏈式前向星，邏輯等價，但 vector 版更現代、不易越界。

複雜度

• 時間：O(E V²) 一般情況，單位容量網絡 O(E√V)，實際極快。
• 空間：O(E + V)

總結

POJ 1273 是驗證 Dinic 實現正確性的標準桿子。掌握分層圖構建、當前弧優化、反向邊更新三大核心，即可解決絕大多數最大流問題。建議熟練背誦上述模板，比賽中可直接複用。