HDU 3549 Flow Problem 最大流模板題 Dinic實現

問題描述

標準最大流問題：給定有向圖 n 個節點，m 條邊，每條邊有容量。求 1 號節點到 n 號節點的最大流。

Dinic 算法模板

struct Edge { int to, cap, next; } e[MAXE];
int head[MAXV], level[MAXV], cur[MAXV], ecnt;

void add_edge(int u, int v, int c) {
    e[ecnt] = {v, c, head[u]}; head[u] = ecnt++;
    e[ecnt] = {u, 0, head[v]}; head[v] = ecnt++;
}

bool bfs(int s, int t) {
    fill(level, level+MAXV, -1);
    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 > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] != -1;
}

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

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

關鍵優化

• 當前弧優化：cur[u] 記錄下次從 u 開始搜索的邊，避免重複遍歷飽和邊
• 分層圖：BFS 構建層次，DFS 只沿層次遞增邊搜索，保證每次增廣路長度遞增
• 鄰接表存儲：反向邊用 i^1 訪問，節省內存

複雜度

一般圖 O(V²)；單位容量網路/二分圖 O(E√V)；實際運行極快。