HDU 1532 Drainage Ditches：最大流模板題 (ISAP/Dinic/EK)

問題描述

有向圖 N 條溝渠，M 個交匯點。1 為池塘，M 為溪流。每條溝渠單向，容量 C_i。求最大流量。N≤200, M≤200。

三種最大流實現對比

1. ISAP (改進最短增廣路) - 推薦

距離標號 + Gap 優化 + 當前弧優化。代碼較長但極快，適合稠密圖。

2. Push-Relabel (HLPP) - 理論最優

預流 + 最高標號優化 + Gap。無需分層圖，實際常比 ISAP 更快。

3. Edmonds-Karp (BFS 增廣) - 最簡單

O(VE^2)，V≤200, E≤200 時 8e6 操作，完全夠用。代碼最短，適合比賽現場打。

EK 核心代碼 (鄰接矩陣)

int cap[205][205], flow[205][205], pre[205], augment[205];
bool bfs(int s, int t, int n) {
    fill(pre, pre+n+1, -1);
    augment[s] = INF;
    queue q; q.push(s);
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for (int v=1;v<=n;v++)
            if (pre[v]==-1 && cap[u][v]-flow[u][v]>0) {
                pre[v]=u;
                augment[v]=min(augment[u], cap[u][v]-flow[u][v]);
                if (v==t) return true;
                q.push(v);
            }
    }
    return false;
}
int maxflow(int s, int t, int n) {
    int ans=0;
    while (bfs(s,t,n)) {
        ans += augment[t];
        for (int v=t; v!=s; v=pre[v]) {
            flow[pre[v]][v] += augment[t];
            flow[v][pre[v]] -= augment[t];
        }
    }
    return ans;
}

關鍵點

• 多測試用例讀到 EOF。
• 並行邊容量疊加 cap[u][v] += c。
• 輸出 long long 格式 %lld 或 %I64d。

總結

HDU 1532 是最大流入門必刷模板題。三種算法各有優勢：EK 代碼最短易記，ISAP 綜合性能最強，Push-Relabel 理論最優。建議熟練掌握 EK 與 ISAP 兩套模板。