Max Flow (Dinic)

Wiki › Thuật toán › Luồng mạng (Network Flow)

huunguyen · Last updated 8, Tháng 4, 2026, 15:32

Bài toán Max Flow: tìm luồng cực đại từ nguồn $s$ đến đích $t$ trong mạng có sức chứa. Thuật toán Dinic có độ phức tạp $O (V^{2} E)$ tổng quát, và $O (E \sqrt{V})$ cho đồ thị đơn vị (unit capacity).

Cài đặt — Dinic

struct MaxFlow {
    struct Edge { int to, rev; long long cap; };
    vector<vector<Edge>> graph;
    vector<int> level, iter;
    int n;

    MaxFlow(int n) : n(n), graph(n), level(n), iter(n) {}

    void add_edge(int from, int to, long long cap) {
        graph[from].push_back({to, (int)graph[to].size(), cap});
        graph[to].push_back({from, (int)graph[from].size()-1, 0});
    }

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

    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        for (int& i = iter[v]; i < (int)graph[v].size(); i++) {
            Edge& e = graph[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                long long d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(iter.begin(), iter.end(), 0);
            long long d;
            while ((d = dfs(s, t, LLONG_MAX)) > 0) flow += d;
        }
        return flow;
    }
};

Ví dụ sử dụng

int main() {
    int n, m; cin >> n >> m;   // n đỉnh, m cạnh
    MaxFlow mf(n);

    for (int i = 0; i < m; i++) {
        int u, v, c; cin >> u >> v >> c;
        mf.add_edge(u, v, c);   // có hướng
        // mf.add_edge(v, u, c); // vô hướng: thêm cả chiều ngược
    }

    int s, t; cin >> s >> t;
    cout << mf.max_flow(s, t) << "\n";
}

Min Cut

Sau khi chạy max flow, lát cắt cực tiểu là tập cạnh từ đỉnh đạt được từ $s$ (trong residual graph) đến đỉnh không đạt được:

// Tìm min cut sau khi đã chạy max_flow
vector<bool> reachable(n, false);
// BFS/DFS trên residual graph từ s
queue<int> q;
reachable[s] = true; q.push(s);
while (!q.empty()) {
    int v = q.front(); q.pop();
    for (auto& e : mf.graph[v])
        if (e.cap > 0 && !reachable[e.to]) {
            reachable[e.to] = true;
            q.push(e.to);
        }
}
// Cạnh (u,v) nằm trong min cut khi reachable[u] && !reachable[v]

Độ phức tạp

Thuật toán	Độ phức tạp
Ford-Fulkerson (BFS = Edmonds-Karp)	$O (V E^{2})$
Dinic	$O (V^{2} E)$
Dinic (unit capacity)	$O (E \sqrt{V})$
Push-Relabel	$O (V^{3})$ hoặc $O (V^{2} \sqrt{E})$

Trong thực tế, Dinic thường nhanh hơn lý thuyết nhiều.

Bình luận

Không có bình luận tại thời điểm này.