Max Flow (Dinic)

Bài toán luồng cực đại (maximum flow): cho một mạng có hướng với nguồn $s$ và đích $t$, mỗi cạnh $(u,v)$ có sức chứa $c(u,v)\ge 0$. Ta cần đẩy một "luồng" từ $s$ tới $t$ sao cho lượng đi qua mỗi cạnh không vượt quá sức chứa, lượng vào mỗi đỉnh (trừ $s,t$) bằng lượng ra, và tổng luồng ra khỏi $s$ là lớn nhất.

Thuật toán Dinic giải bài này trong $O(V^{2}E)$ tổng quát — nhanh hơn nhiều so với Edmonds-Karp ($O(V{E}^2)$) trên đồ thị dày, và đạt $O(E\sqrt{V})$ trên mạng sức chứa đơn vị (dùng cho ghép cặp hai phía). Trong thực tế Dinic chạy rất nhanh, thường là lựa chọn mặc định cho mọi bài luồng ở mức thi đấu.

Ý tưởng / Trực giác

Mọi thuật toán luồng đều dựa trên ý tưởng đường tăng luồng (augmenting path): tìm một đường từ $s$ tới $t$ mà mọi cạnh còn "chỗ trống", rồi đẩy thêm luồng dọc theo nó. Lặp lại đến khi không còn đường nào.

Cạnh ngược và đồ thị thặng dư (residual graph). Mấu chốt khiến thuật toán đúng là khái niệm cạnh ngược. Khi ta đẩy $f$ đơn vị qua cạnh $u\to v$, ta tạo (hoặc tăng) một cạnh ngược $v\to u$ với sức chứa $f$. Cạnh ngược cho phép thuật toán "hối lỗi": một lần đẩy sau có thể đi ngược lại để hủy bớt luồng đã đẩy sai, nhờ đó không bao giờ bị "kẹt" ở một phương án chưa tối ưu. Sức chứa còn lại của một cạnh trong đồ thị thặng dư gọi là residual $=c-f$.

Vì sao dừng lại là tối ưu — định lý Max-Flow Min-Cut. Khi không còn đường tăng nào, gọi $S$ là tập đỉnh còn đến được từ $s$ trong đồ thị thặng dư, $T$ là phần còn lại ($t\in T$). Mọi cạnh từ $S$ sang $T$ đều đã bão hòa (residual $=0$), nên tổng luồng đúng bằng tổng sức chứa các cạnh cắt ngang $(S,T)$. Vì luồng bất kỳ không thể vượt quá sức chứa của bất kỳ lát cắt nào, ta vừa tìm được luồng bằng lát cắt nhỏ nhất — đó chính là cực đại. Đây cũng là lý do bài "chặn ít đường nhất" (min-cut) giải được bằng max flow.

Dinic nhanh ở đâu. Edmonds-Karp dùng BFS tìm từng đường một. Dinic gộp lại theo hai tầng:

1. BFS xếp tầng (level graph): gán $level[v]$ = khoảng cách ngắn nhất từ $s$ tới $v$ theo số cạnh trong đồ thị thặng dư. Chỉ giữ những cạnh đi "tiến lên" đúng một tầng. Mỗi pha như vậy, đường ngắn nhất $s\to t$ dài thêm ít nhất 1, nên có tối đa $O(V)$ pha.
2. DFS chặn (blocking flow): trong cùng một level graph, DFS đẩy luồng cho đến khi không còn đường tiến nào từ $s$ tới $t$. Con trỏ iter[v] ghi nhớ cạnh kế tiếp cần thử ở mỗi đỉnh để không xét lại cạnh đã chết — nhờ đó mỗi pha chỉ tốn $O(VE)$.

Kết hợp lại: $O(V)$ pha $\times O(VE)$ mỗi pha $=O(V^{2}E)$.

Ví dụ chạy tay

Mạng 4 đỉnh ($s=1$, $t=4$), các cạnh (sức chứa):

        [3]
   1 -------> 2
   |          |
[4]|          |[2]
   v          v
   3 -------> 4
        [5]

Cạnh: $1\to 2(3),1\to 3(4),2\to 4(2),3\to 4(5)$. Mỗi cạnh kèm một cạnh ngược sức chứa 0.

Pha 1 — BFS xếp tầng. Từ $s=1$:

đỉnh :  1   2   3   4
level:  0   1   1   2

level[4]=2 >= 0 nên còn đường. DFS từ 1:

• Thử cạnh $1\to 2$ (cap 3): xuống 2 → thử $2\to 4$ (cap 2): tới đích. Đẩy $min(3,2)=2$. Cập nhật: $1\to 2$ còn $1$, ngược $2\to 1$ thành $2$; $2\to 4$ còn $0$ (bão hòa), ngược $4\to 2$ thành $2$.
• DFS tiếp từ 1: cạnh $1\to 2$ còn 1, xuống 2; nhưng $2\to 4$ đã bão hòa và 2 không còn cạnh tiến nào → iter[2] vượt hết → 2 "chết". Quay lui, iter[1] chuyển sang $1\to 3$.
• $1\to 3$ (cap 4): xuống 3 → $3\to 4$ (cap 5): tới đích. Đẩy $min(4,5)=4$. Cập nhật: $1\to 3$ còn $0$, $3\to 4$ còn $1$.
• DFS lần nữa: $1\to 2$ còn 1 nhưng nhánh qua 2 đã chết; $1\to 3$ bão hòa → không còn đường. Kết thúc pha.

Luồng sau pha 1: $2+4=6$. Residual hiện tại:

   1 --1--> 2          (ngược 2->1 = 2)
   1 --0--> 3          (bão hòa)
   2 --0--> 4          (bão hòa; ngược 4->2 = 2)
   3 --1--> 4

Pha 2 — BFS lại. Từ 1 chỉ còn cạnh tiến $1\to 2$ (cap 1). Từ 2: cạnh $2\to 4$ bão hòa, cạnh ngược $2\to 1$ quay về 1 (đã thăm). Vậy không tới được 4 → level[4] = -1. Hết đường tăng.

Kết quả: luồng cực đại $=6$. Lát cắt nhỏ nhất: $S=\{1,2\}$ (đến được từ 1), $T=\{3,4\}$; các cạnh cắt $1\to 3(4)$ và $2\to 4(2)$ có tổng $=6$ — đúng bằng luồng, xác nhận tối ưu.

Cài đặt

#include <bits/stdc++.h>
using namespace std;

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) {}

    // Thêm cạnh có hướng from->to (cap) kèm cạnh ngược (cap 0).
    // rev là chỉ số của cạnh đối ứng trong danh sách kề của đỉnh kia,
    // dùng để truy cập nhanh khi cập nhật luồng.
    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});
    }

    // BFS xếp tầng: tính khoảng cách ngắn nhất (số cạnh) từ s
    // chỉ qua các cạnh còn residual > 0. Trả về true nếu t còn tới được.
    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;
    }

    // DFS đẩy luồng trong level graph. iter[v] bỏ qua các cạnh đã chết
    // (đã xét xong) nên mỗi cạnh chỉ bị duyệt một lần mỗi pha.
    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];
            // chỉ đi tiến đúng một tầng (level[e.to] = level[v]+1)
            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;                       // giảm cạnh xuôi
                    graph[e.to][e.rev].cap += d;      // tăng cạnh ngược
                    return d;
                }
            }
        }
        return 0; // không còn đường tiến từ v -> v "chết" trong pha này
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {            // mỗi vòng = một pha (một level graph)
            fill(iter.begin(), iter.end(), 0);
            long long d;
            while ((d = dfs(s, t, LLONG_MAX)) > 0) flow += d; // đẩy luồng chặn
        }
        return flow;
    }
};

int main() {
    int n, m; 
    cin >> n >> m;
    MaxFlow mf(n + 1);   // đánh số đỉnh 1..n
    for (int i = 0; i < m; i++) {
        int u, v; long long c; 
        cin >> u >> v >> c;
        mf.add_edge(u, v, c);
    }
    cout << mf.max_flow(1, n) << "\n";
}

Khôi phục lát cắt nhỏ nhất (min-cut): sau khi chạy max_flow, gọi lại bfs(s, t); mọi đỉnh $u$ có level[u] != -1 thuộc $S$. Cạnh gốc $(u,v)$ với $u\in S,v\notin S$ chính là cạnh thuộc lát cắt. (Để phân biệt cạnh gốc với cạnh ngược, có thể đánh dấu cạnh ngược bằng cap ban đầu $=0$, hoặc lưu thêm cờ.)

Độ phức tạp

Bộ nhớ: $O(V+E)$ — danh sách kề lưu mỗi cạnh hai lần (xuôi + ngược), cộng hai mảng level, iter cỡ $V$. Lưu ý cận $O(V^{2}E)$ là cận xấu nhất rất bi quan; trên dữ liệu thực Dinic gần như luôn nhanh hơn nhiều.

⚠️ Lỗi thường gặp

• Tràn số (overflow): tổng luồng có thể tới $\sum$ sức chứa, dễ vượt int. Khi $c\le {10}^9$ và nhiều cạnh, luồng có thể $>2·{10}^9$. Dùng long long cho cap và biến tích lũy flow, và khởi tạo f = LLONG_MAX (không phải INT_MAX) khi gọi DFS.
• Cạnh ngược sai chỉ số rev: khi thêm cạnh phải đặt rev đúng vị trí cạnh đối ứng. Thứ tự hai dòng push_back rất quan trọng: cạnh xuôi trỏ tới graph[to].size() trước khi thêm cạnh ngược; cạnh ngược trỏ tới graph[from].size()-1 sau khi đã thêm cạnh xuôi. Đảo thứ tự sẽ làm cập nhật luồng vào nhầm cạnh → kết quả sai âm thầm.
• Quên reset iter mỗi pha: iter phải đặt lại về 0 sau mỗi lần BFS thành công, không phải một lần duy nhất. Quên reset khiến DFS bỏ qua cạnh hợp lệ ở pha sau → ra luồng thiếu.
• Cạnh hai chiều (vô hướng): một cạnh vô hướng sức chứa $c$ phải mô hình bằng hai cạnh có hướng, mỗi chiều residual ban đầu $c$. Cách phổ biến: add_edge(u, v, c) rồi add_edge(v, u, c); hoặc thêm một cạnh với cả hai nửa cap $=c$. Đặt cạnh ngược cap $0$ như cạnh có hướng sẽ tính thiếu một chiều (bài min-cut trên đồ thị vô hướng rất dễ dính lỗi này).
• DFS không trả min(f, e.cap): phải lan truyền cận luồng nhỏ dần xuống. Truyền nguyên f rồi mới trừ ở đáy sẽ đẩy quá sức chứa của cạnh giữa đường.
• Điều kiện tầng dùng sai dấu: phải là level[v] < level[e.to] (đi tiến đúng một tầng). Dùng != hoặc <= sẽ cho phép đi ngang/đi lùi, phá vỡ tính chặn của pha và có thể lặp vô hạn.

Biến thể / Mở rộng

• Lát cắt nhỏ nhất (min-cut): đúng bằng max flow (xem phần khôi phục ở trên). Dạng "chặn số cạnh tối thiểu" = max flow với mọi cạnh sức chứa 1.
• Ghép cặp hai phía (bipartite matching): thêm nguồn $s$ nối tới mọi đỉnh trái (cap 1), mọi đỉnh phải nối tới đích $t$ (cap 1), cạnh giữa hai phía cap 1; max flow = số cặp lớn nhất.
• Đỉnh có sức chứa: tách mỗi đỉnh $v$ thành $v_{in}\to v_{out}$ với cạnh sức chứa bằng giới hạn của đỉnh.
• Luồng chi phí nhỏ nhất (min-cost max-flow / MCMF): khi mỗi cạnh có thêm chi phí/đơn vị, thay BFS bằng SPFA/Dijkstra để chọn đường tăng rẻ nhất. Dùng cho bài "vận chuyển $k$ kiện hàng với tổng chi phí nhỏ nhất".

Bài tập luyện

• Tốc Độ Tải Xuống (downloadspd) — (Kỳ cựu) max flow $s$–$t$ thuần túy, áp thẳng Dinic; bài nhập môn lý tưởng để kiểm chứng cài đặt (nhớ long long vì $c\le {10}^9$).
• Vũ Hội Học Đường (schooldance) — (Kỳ cựu) ghép cặp hai phía qua mô hình luồng sức chứa đơn vị, còn phải in ra các cặp được ghép (truy vết cạnh giữa đã bão hòa).
• Đuổi Bắt Cảnh Sát (policechase) — (Kỳ cựu) min-cut trên đồ thị vô hướng (mỗi đường = 1 cạnh hai chiều cap 1); luyện định lý max-flow min-cut và khôi phục tập cạnh cắt.
• Giao Hàng (parceldeliv) — (Chuyên gia) biến thể luồng chi phí nhỏ nhất (MCMF): đẩy đúng $k$ đơn vị với tổng chi phí cực tiểu, mở rộng tự nhiên từ Dinic sang đường tăng rẻ nhất.