Bài 41: Network Flow — Luồng Cực Đại¶

1. Bài toán luồng cực đại¶

Bản chất vấn đề¶

Cho đồ thị có hướng \(G = (V, E)\) với:

Nguồn \(s\): đỉnh bắt đầu
Bể \(t\): đỉnh kết thúc
Dung lượng \(c(u,v)\): lượng tối đa chảy qua cạnh \((u,v)\)

Một luồng hợp lệ \(f\) phải thỏa mãn hai ràng buộc:

Ràng buộc dung lượng: \(0 \le f(u,v) \le c(u,v)\) với mọi cạnh
Bảo toàn luồng: Với mọi đỉnh \(v \notin \{s, t\}\), tổng luồng vào bằng tổng luồng ra:

\[\sum_{u} f(u,v) = \sum_{w} f(v,w)\]

Mục tiêu: Tìm giá trị luồng cực đại \(|f| = \sum_{v} f(s,v)\).

Tư duy cốt lõi¶

Ẩn dụ đơn giản: hình dung một hệ thống ống nước. Nước chảy từ nguồn \(s\) qua các ống có giới hạn dung lượng đến bể \(t\). Câu hỏi là: tối đa bao nhiêu nước có thể chảy qua hệ thống?

Minh họa một mạng luồng nhỏ:

graph LR
    s((s)) -->|f=8, c=10| A((A))
    s((s)) -->|f=5, c=10| B((B))
    A -->|f=4, c=10| C((C))
    A -->|f=4, c=10| B
    B -->|f=9, c=10| C
    C -->|f=10, c=10| t((t))
    B -->|f=0, c=10| t

Trong sơ đồ trên, mỗi cạnh hiển thị \(f/c\) (luồng hiện tại / dung lượng tối đa).

2. Ford-Fulkerson & Đồ thị dư¶

Bản chất vấn đề¶

Ford-Fulkerson là phương pháp (framework) tổng quát, không phải một thuật toán cụ thể. Mọi thuật toán luồng cực đại đều dựa trên ý tưởng này.

Tư duy cốt lõi¶

Bước 1: Bắt đầu với luồng \(f = 0\) trên mọi cạnh.

Bước 2: Tìm một đường tăng luồng (augmenting path) từ \(s\) đến \(t\) trong đồ thị dư.

Bước 3: Tăng luồng dọc theo đường đó một lượng bằng bottleneck (cạnh nhỏ nhất trên đường đi).

Bước 4: Lặp lại cho đến khi không còn đường tăng luồng nào.

Đồ thị dư (Residual Graph)¶

Đồ thị dư là chìa khóa của toàn bộ lý thuyết. Với mỗi cạnh \((u,v)\) có dung lượng \(c\) và luồng \(f\):

Cạnh thuận: từ \(u\) đến \(v\) với dung lượng dư \(c - f\) (còn đẩy thêm được bao nhiêu)
Cạnh ngược: từ \(v\) đến \(u\) với dung lượng dư \(f\) (có thể "rút lại" bao nhiêu luồng)

Tại sao cần cạnh ngược? Khi ta đẩy luồng sai đường, cạnh ngược cho phép "hủy" luồng đó và đẩy lại theo hướng khác. Đây là cơ chế cốt lõi đảm bảo thuật toán luôn tìm được lời giải tối ưu.

Ví dụ minh họa¶

Xem xét mạng luồng ban đầu với 2 đường đi từ \(s\) đến \(t\):

graph LR
    s((s)) -->|c=10| A((A))
    s((s)) -->|c=10| B((B))
    A -->|c=5| t((t))
    B -->|c=10| t

Lần 1: Tìm đường \(s \to A \to t\), bottleneck = 5. Đẩy luồng 5.

Lần 2: Tìm đường \(s \to B \to t\), bottleneck = 10. Đẩy luồng 10.

Tổng luồng = 15 = dung lượng cắt nhỏ nhất \(\{s\}\) vs \(\{A, B, t\}\).

Phân tích tính đúng đắn¶

Định lý Max-Flow Min-Cut (Ford-Fulkerson 1956): Luồng cực đại = Giá trị cắt nhỏ nhất.

Cắt \(s\)-\(t\) là cách chia đỉnh thành hai tập \(S\) và \(T\) sao cho \(s \in S\), \(t \in T\). Giá trị cắt là tổng dung lượng các cạnh đi từ \(S\) sang \(T\):

\[c(S, T) = \sum_{u \in S, v \in T} c(u,v)\]

Minh họa cắt nhỏ nhất:

graph LR
    subgraph S["Tập S"]
        s((s))
    end
    subgraph T["Tập T"]
        A((A))
        t((t))
    end
    s -->|10| A
    s -->|5| t
    A -->|3| t

Giá trị cắt = \(10 + 5 = 15\). Luồng cực đại không thể vượt quá 15, và ta đã đạt được 15.

Chứng minh (phác thảo):

Luồng \(\le\) cắt: Mọi đơn vị luồng từ \(s\) đến \(t\) phải đi qua ít nhất một cạnh trong cắt. Tổng luồng qua cắt \(\le\) tổng dung lượng cắt.
Luồng = cắt: Khi thuật toán dừng, tồn tại cắt mà luồng = giá trị cắt. Cạnh cắt đầy (\(f = c\)), các cạnh khác cân bằng.

Đánh giá độ phức tạp¶

Nếu dùng DFS để tìm đường tăng, thuật toán có thể chạy vô hạn khi dung lượng là số vô tỉ. Với dung lượng nguyên, độ phức tạp là \(O(E \cdot f^*)\) trong đó \(f^*\) là luồng cực đại — có thể rất lớn.

3. Edmonds-Karp (BFS)¶

Bản chất vấn đề¶

Edmonds-Karp là phiên bản cụ thể của Ford-Fulkerson, dùng BFS thay vì DFS để tìm đường tăng luồng. Sự thay đổi đơn giản này đảm bảo thuật toán luôn dừng trong thời gian đa thức.

Tư duy cốt lõi¶

Thay vì tìm đường tăng bất kỳ, ta luôn tìm đường tăng ngắn nhất (ít cạnh nhất) bằng BFS.

Tại sao ngắn nhất lại tốt? Khi mỗi bước chỉ tìm đường ngắn nhất, ta có thể chứng minh rằng khoảng cách từ \(s\) đến \(t\) trong đồ thị dư không giảm sau mỗi lần tăng luồng. Điều này giới hạn số lần tăng luồng.

Phân tích tính đúng đắn¶

Bổ đề quan trọng: Trong Edmonds-Karp, khoảng cách ngắn nhất từ \(s\) đến \(t\) trong đồ thị dư (gọi là \(\delta\)) không giảm sau mỗi lần tăng luồng.

Chứng minh ý tưởng: Giả sử sau khi tăng luồng, \(\delta\) giảm. Xét đường tăng cuối cùng trước khi \(\delta\) giảm. Đường đó phải đi qua ít nhất một cạnh "bị đầy" (trở thành cạnh ngược mới). Phân tích các trường hợp cho thấy điều này mâu thuẫn.

Hệ quả: Mỗi cạnh chỉ có thể trở thành "critical edge" (cạnh bị đầy trên đường tăng) tối đa \(O(V)\) lần. Tổng số lần tăng luồng là \(O(VE)\).

Đánh giá độ phức tạp¶

Mỗi lần BFS: \(O(E)\)
Số lần tăng luồng: \(O(VE)\)
Tổng: \(O(VE^2)\)

Cài đặt¶

C++Python

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

struct Edge {
    int to, rev;            // đỉnh đích, chỉ số cạnh ngược
    long long cap, flow;    // dung lượng, luồng hiện tại
};

class EdmondsKarp {
public:
    int n;
    vector<vector<Edge>> adj;

    EdmondsKarp(int n) : n(n), adj(n + 1) {}

    void addEdge(int u, int v, long long cap) {
        adj[u].push_back({v, (int)adj[v].size(), cap, 0});      // cạnh thuận
        adj[v].push_back({u, (int)adj[u].size() - 1, 0, 0});    // cạnh ngược dung lượng 0
    }

    long long maxFlow(int s, int t) {
        long long total = 0;
        while (true) {
            vector<int> parent(n + 1, -1);       // đỉnh cha trên đường tăng
            vector<int> parentEdge(n + 1, -1);   // chỉ số cạnh từ cha đến đỉnh
            queue<int> q;
            q.push(s);
            parent[s] = s;

            while (!q.empty() && parent[t] == -1) {  // BFS tìm đường tăng luồng
                int u = q.front(); q.pop();
                for (int i = 0; i < (int)adj[u].size(); i++) {
                    Edge& e = adj[u][i];
                    if (parent[e.to] == -1 && e.cap - e.flow > 0) {  // còn dung lượng dư
                        parent[e.to] = u;
                        parentEdge[e.to] = i;
                        q.push(e.to);
                    }
                }
            }

            if (parent[t] == -1) break;  // không còn đường tăng

            long long bottleneck = LLONG_MAX;
            for (int v = t; v != s; v = parent[v]) {   // tìm bottleneck
                int u = parent[v];
                int idx = parentEdge[v];
                bottleneck = min(bottleneck, adj[u][idx].cap - adj[u][idx].flow);
            }

            for (int v = t; v != s; v = parent[v]) {   // tăng luồng dọc đường đi
                int u = parent[v];
                int idx = parentEdge[v];
                adj[u][idx].flow += bottleneck;
                adj[v][adj[u][idx].rev].flow -= bottleneck;  // cập nhật cạnh ngược
            }

            total += bottleneck;
        }
        return total;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    EdmondsKarp mf(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long cap;
        cin >> u >> v >> cap;
        mf.addEdge(u, v, cap);
    }

    cout << mf.maxFlow(1, n) << "\n";
    return 0;
}

from collections import deque

class EdmondsKarp:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n + 1)]

    def add_edge(self, u, v, cap):
        forward = [v, cap, 0, len(self.adj[v])]       # cạnh thuận
        backward = [u, 0, 0, len(self.adj[u])]         # cạnh ngược dung lượng 0
        self.adj[u].append(forward)
        self.adj[v].append(backward)

    def max_flow(self, s, t):
        total = 0
        while True:
            parent = [-1] * (self.n + 1)               # đỉnh cha trên đường tăng
            parent_edge = [-1] * (self.n + 1)           # chỉ số cạnh từ cha
            q = deque([s])
            parent[s] = s

            while q and parent[t] == -1:               # BFS tìm đường tăng
                u = q.popleft()
                for i, e in enumerate(self.adj[u]):
                    v, cap, flow, rev = e
                    if parent[v] == -1 and cap - flow > 0:  # còn dung lượng dư
                        parent[v] = u
                        parent_edge[v] = i
                        q.append(v)

            if parent[t] == -1:                        # không còn đường tăng
                break

            bottleneck = float('inf')
            v = t
            while v != s:                              # tìm bottleneck
                u = parent[v]
                idx = parent_edge[v]
                bottleneck = min(bottleneck, self.adj[u][idx][1] - self.adj[u][idx][2])
                v = u

            v = t
            while v != s:                              # tăng luồng dọc đường đi
                u = parent[v]
                idx = parent_edge[v]
                self.adj[u][idx][2] += bottleneck       # cập nhật luồng cạnh thuận
                rev_idx = self.adj[u][idx][3]
                self.adj[v][rev_idx][2] -= bottleneck   # cập nhật cạnh ngược
                v = u

            total += bottleneck
        return total

n, m = map(int, input().split())
mf = EdmondsKarp(n)
for _ in range(m):
    u, v, cap = map(int, input().split())
    mf.add_edge(u, v, cap)
print(mf.max_flow(1, n))

4. Dinic's Algorithm¶

Bản chất vấn đề¶

Edmonds-Karp chạy \(O(VE^2)\) — mỗi BFS tìm một đường tăng. Với đồ thị lớn (hàng chục nghìn đỉnh), ta cần thuật toán nhanh hơn. Dinic cải thiện bằng cách mỗi lần BFS xây dựng toàn bộ đồ thị tầng, sau đó dùng DFS đẩy nhiều đường tăng cùng lúc.

Tư duy cốt lõi¶

Thuật toán gồm 2 giai đoạn lặp lại:

Giai đoạn 1 — Xây đồ thị tầng (BFS):

Dùng BFS đánh số "tầng" \(level[v]\) cho mỗi đỉnh. Chỉ giữ cạnh \((u,v)\) nào thỏa mãn \(level[v] = level[u] + 1\).

Giai đoạn 2 — Tìm Blocking Flow (DFS):

Trên đồ thị tầng, dùng DFS tìm nhiều đường tăng cùng lúc cho đến khi không còn đường nào. Kết quả gọi là blocking flow — luồng mà không còn đường tăng nào trên đồ thị tầng.

graph LR
    subgraph L0["Tầng 0"]
        s((s))
    end
    subgraph L1["Tầng 1"]
        A((A))
        B((B))
    end
    subgraph L2["Tầng 2"]
        t((t))
    end
    s --> A
    s --> B
    A --> t
    B --> t

Sau khi blocking flow được tìm, ít nhất một cạnh trên mỗi đường tăng bị đầy. Đồ thị tầng cũ không còn hữu dụng → quay lại giai đoạn 1.

Phân tích tính đúng đắn¶

Bổ đề: Khoảng cách \(level[t]\) từ \(s\) đến \(t\) trong đồ thị dư tăng ít nhất 1 sau mỗi giai đoạn.

Chứng minh: Khi blocking flow được tìm, mọi đường tăng ngắn nhất trong đồ thị tầng đều bị chặn. Đường tăng mới (nếu có) phải đi qua cạnh ngược mới tạo ra, tức là phải đi qua đỉnh ở tầng cao hơn → \(level[t]\) tăng.

Hệ quả: Số giai đoạn (số lần BFS) tối đa là \(V - 1\).

Current Edge Optimization (Con trỏ ptr):

Khi DFS tại đỉnh \(u\) duyệt xong cạnh thứ \(i\) mà không đẩy được luồng, lần sau không cần duyệt lại cạnh \(0..i\). Dùng mảng \(ptr[u]\) để nhớ vị trí đã duyệt. Nếu không dùng \(ptr\), Dinic có thể chậm đi rất nhiều!

Đánh giá độ phức tạp¶

Số lần BFS: \(O(V)\)
Mỗi giai đoạn DFS tổng cộng: \(O(VE)\) (mỗi cạnh được duyệt tối đa một lần nhờ \(ptr\))
Tổng: \(O(V^2 E)\)

Trường hợp đặc biệt — Đồ thị hai phía: \(O(E\sqrt{V})\). Vì mỗi đường tăng trong bipartite graph có độ dài cố định, số giai đoạn chỉ là \(O(\sqrt{V})\).

Cài đặt¶

C++Python

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

struct Edge {
    int to, rev;
    long long cap, flow;
};

class Dinic {
public:
    int n;
    vector<vector<Edge>> adj;
    vector<int> level;       // tầng của mỗi đỉnh trong đồ thị tầng
    vector<int> ptr;         // con trỏ current edge optimization

    Dinic(int n) : n(n), adj(n + 1), level(n + 1), ptr(n + 1) {}

    void addEdge(int u, int v, long long cap, bool directed = true) {
        adj[u].push_back({v, (int)adj[v].size(), cap, 0});
        adj[v].push_back({u, (int)adj[u].size() - 1, directed ? 0 : cap, 0});  // cạnh ngược
    }

    bool bfs(int s, int t) {                    // xây đồ thị tầng
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        queue<int> q;
        q.push(s);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : adj[u]) {
                if (level[e.to] == -1 && e.cap - e.flow > 0) {
                    level[e.to] = level[u] + 1; // gán tầng cho đỉnh kề
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;                  // true nếu còn đường tới t
    }

    long long dfs(int u, int t, long long pushed) {  // tìm blocking flow
        if (u == t || pushed == 0) return pushed;

        for (int& cid = ptr[u]; cid < (int)adj[u].size(); cid++) {  // current edge optimization
            Edge& e = adj[u][cid];
            if (level[e.to] != level[u] + 1) continue;  // chỉ đi theo tầng tăng dần
            if (e.cap - e.flow <= 0) continue;

            long long tr = dfs(e.to, t, min(pushed, e.cap - e.flow));
            if (tr == 0) continue;

            e.flow += tr;                       // tăng luồng cạnh thuận
            adj[e.to][e.rev].flow -= tr;        // giảm luồng cạnh ngược
            return tr;
        }
        return 0;
    }

    long long maxFlow(int s, int t) {
        long long total = 0;
        while (bfs(s, t)) {                     // xây đồ thị tầng
            fill(ptr.begin(), ptr.end(), 0);    // reset con trỏ
            while (long long pushed = dfs(s, t, LLONG_MAX)) {
                total += pushed;                // gộp luồng đẩy được
            }
        }
        return total;
    }

    vector<bool> minCut(int s) {                // tìm tập đỉnh thuộc phía S của lát cắt
        vector<bool> visited(n + 1, false);
        queue<int> q;
        q.push(s);
        visited[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : adj[u]) {
                if (!visited[e.to] && e.cap - e.flow > 0) {
                    visited[e.to] = true;
                    q.push(e.to);
                }
            }
        }
        return visited;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    Dinic dinic(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long cap;
        cin >> u >> v >> cap;
        dinic.addEdge(u, v, cap);
    }

    cout << dinic.maxFlow(1, n) << "\n";
    return 0;
}

from collections import deque
import sys
input = sys.stdin.readline

class Dinic:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n + 1)]
        self.level = [-1] * (n + 1)          # tầng của mỗi đỉnh
        self.ptr = [0] * (n + 1)             # con trỏ current edge optimization

    def add_edge(self, u, v, cap, directed=True):
        forward = [v, cap, 0, len(self.adj[v])]        # cạnh thuận
        backward = [u, 0 if directed else cap, 0, len(self.adj[u])]  # cạnh ngược
        self.adj[u].append(forward)
        self.adj[v].append(backward)

    def bfs(self, s, t):                      # xây đồ thị tầng
        self.level = [-1] * (self.n + 1)
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for e in self.adj[u]:
                v, cap, flow, rev = e
                if self.level[v] == -1 and cap - flow > 0:
                    self.level[v] = self.level[u] + 1  # gán tầng
                    q.append(v)
        return self.level[t] != -1

    def dfs(self, u, t, pushed):              # tìm blocking flow
        if u == t or pushed == 0:
            return pushed
        while self.ptr[u] < len(self.adj[u]):  # current edge optimization
            e = self.adj[u][self.ptr[u]]
            v, cap, flow, rev = e
            if self.level[v] != self.level[u] + 1 or cap - flow <= 0:
                self.ptr[u] += 1
                continue
            tr = self.dfs(v, t, min(pushed, cap - flow))
            if tr == 0:
                self.ptr[u] += 1
                continue
            e[2] += tr                          # tăng luồng cạnh thuận
            self.adj[v][rev][2] -= tr           # giảm luồng cạnh ngược
            return tr
        return 0

    def max_flow(self, s, t):
        total = 0
        while self.bfs(s, t):                   # xây đồ thị tầng
            self.ptr = [0] * (self.n + 1)       # reset con trỏ
            while True:
                pushed = self.dfs(s, t, float('inf'))
                if pushed == 0:
                    break
                total += pushed
        return total

    def min_cut(self, s):                       # tìm lát cắt nhỏ nhất
        visited = [False] * (self.n + 1)
        visited[s] = True
        q = deque([s])
        while q:
            u = q.popleft()
            for e in self.adj[u]:
                v, cap, flow, rev = e
                if not visited[v] and cap - flow > 0:
                    visited[v] = True
                    q.append(v)
        return visited

n, m = map(int, input().split())
dinic = Dinic(n)
for _ in range(m):
    u, v, cap = map(int, input().split())
    dinic.add_edge(u, v, cap)
print(dinic.max_flow(1, n))

5. Min-Cost Max-Flow¶

Bản chất vấn đề¶

Giống max-flow, nhưng mỗi cạnh có thêm chi phí \(cost(u,v)\). Mục tiêu kép:

Đẩy luồng cực đại từ \(s\) đến \(t\)
Trong số các luồng cực đại, chọn luồng có tổng chi phí nhỏ nhất

\[\text{Cost}(f) = \sum_{(u,v) \in E} f(u,v) \cdot cost(u,v)\]

Tư duy cốt lõi¶

Thuật toán Successive Shortest Path:

Bắt đầu với luồng \(f = 0\)
Trong đồ thị dư, mỗi cạnh có cost:
Cạnh thuận \((u,v)\): \(cost(u,v)\)
Cạnh ngược \((v,u)\): \(-cost(u,v)\) (rút luồng → hoàn tiền)
Mỗi bước, tìm đường tăng có chi phí nhỏ nhất bằng SPFA hoặc Dijkstra với potential
Đẩy luồng dọc theo đường đó
Lặp cho đến khi không còn đường tăng

Dijkstra với Potential (Nâng cao):

SPFA chạy worst-case \(O(VE)\) mỗi lần. Để cải thiện, dùng hàm tiềm năng \(h[v]\):

Lần đầu dùng Bellman-Ford/SPFA để tính \(h[v]\)
Các lần sau, trọng số cạnh điều chỉnh thành \(cost(u,v) + h[u] - h[v] \ge 0\)
Dùng Dijkstra thay SPFA → \(O(F \cdot E \log V)\) thay vì \(O(F \cdot VE)\)

Phân tích tính đúng đắn¶

Mỗi bước tìm đường ngắn nhất trong đồ thị dư. Cạnh ngược có cost âm (hoàn tiền), nhưng nhờ potential function, trọng số điều chỉnh luôn không âm → Dijkstra hoạt động đúng.

Khi không còn đường tăng, luồng hiện tại là luồng cực đại. Vì mỗi bước chọn đường chi phí nhỏ nhất, tổng chi phí được tối thiểu hóa trong số các luồng cực đại.

Đánh giá độ phức tạp¶

SPFA: \(O(F \cdot VE)\) trong đó \(F\) là giá trị luồng cực đại
Dijkstra + Potential: \(O(F \cdot E \log V)\)

Cài đặt¶

C++Python

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

struct MCFEdge {
    int to, rev;
    long long cap, flow, cost;
};

class MinCostMaxFlow {
public:
    int n;
    vector<vector<MCFEdge>> adj;
    vector<long long> dist, pot;
    vector<int> parent, parentEdge;
    const long long INF = 1e18;

    MinCostMaxFlow(int n) : n(n), adj(n + 1), dist(n + 1), pot(n + 1),
                            parent(n + 1), parentEdge(n + 1) {}

    void addEdge(int u, int v, long long cap, long long cost) {
        adj[u].push_back({v, (int)adj[v].size(), cap, 0, cost});       // cạnh thuận
        adj[v].push_back({u, (int)adj[u].size() - 1, 0, 0, -cost});    // cạnh ngược chi phí âm
    }

    bool spfa(int s, int t, long long& flow, long long& cost, long long maxFlow) {
        fill(dist.begin(), dist.end(), INF);          // tìm đường đi chi phí nhỏ nhất
        vector<bool> inQueue(n + 1, false);
        dist[s] = 0;
        queue<int> q;
        q.push(s);
        inQueue[s] = true;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            inQueue[u] = false;
            for (int i = 0; i < (int)adj[u].size(); i++) {
                MCFEdge& e = adj[u][i];
                if (e.cap - e.flow > 0 && dist[u] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[u] + e.cost;
                    parent[e.to] = u;
                    parentEdge[e.to] = i;
                    if (!inQueue[e.to]) {
                        q.push(e.to);
                        inQueue[e.to] = true;
                    }
                }
            }
        }

        if (dist[t] == INF) return false;             // không còn đường tăng

        long long pushFlow = maxFlow - flow;
        for (int v = t; v != s; v = parent[v]) {      // tìm bottleneck
            int u = parent[v];
            int idx = parentEdge[v];
            pushFlow = min(pushFlow, adj[u][idx].cap - adj[u][idx].flow);
        }

        for (int v = t; v != s; v = parent[v]) {      // tăng luồng dọc đường đi
            int u = parent[v];
            int idx = parentEdge[v];
            adj[u][idx].flow += pushFlow;
            adj[v][adj[u][idx].rev].flow -= pushFlow;
        }

        flow += pushFlow;
        cost += pushFlow * dist[t];                   // cộng chi phí
        return true;
    }

    pair<long long, long long> mcmf(int s, int t, long long maxFlow = INF) {
        long long flow = 0, cost = 0;
        while (spfa(s, t, flow, cost, maxFlow)) {}    // lặp cho đến khi hết đường tăng
        return {flow, cost};
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    MinCostMaxFlow mcmf(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long cap, cost;
        cin >> u >> v >> cap >> cost;
        mcmf.addEdge(u, v, cap, cost);
    }

    auto [flow, cost] = mcmf.mcmf(1, n);
    cout << flow << " " << cost << "\n";
    return 0;
}

from collections import deque
import sys
input = sys.stdin.readline

class MinCostMaxFlow:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n + 1)]
        self.INF = 10**18

    def add_edge(self, u, v, cap, cost):
        forward = [v, cap, 0, cost, len(self.adj[v])]          # cạnh thuận
        backward = [u, 0, 0, -cost, len(self.adj[u])]          # cạnh ngược chi phí âm
        self.adj[u].append(forward)
        self.adj[v].append(backward)

    def spfa(self, s, t, flow, max_flow):                      # tìm đường chi phí nhỏ nhất
        dist = [self.INF] * (self.n + 1)
        parent = [-1] * (self.n + 1)
        parent_edge = [-1] * (self.n + 1)
        in_queue = [False] * (self.n + 1)
        dist[s] = 0
        q = deque([s])
        in_queue[s] = True

        while q:
            u = q.popleft()
            in_queue[u] = False
            for i, e in enumerate(self.adj[u]):
                v, cap, fl, cost, rev = e
                if cap - fl > 0 and dist[u] + cost < dist[v]:
                    dist[v] = dist[u] + cost
                    parent[v] = u
                    parent_edge[v] = i
                    if not in_queue[v]:
                        q.append(v)
                        in_queue[v] = True

        if dist[t] == self.INF:                                # không còn đường tăng
            return 0, 0

        push = max_flow - flow
        v = t
        while v != s:                                          # tìm bottleneck
            u = parent[v]
            idx = parent_edge[v]
            push = min(push, self.adj[u][idx][1] - self.adj[u][idx][2])
            v = u

        v = t
        while v != s:                                          # tăng luồng dọc đường đi
            u = parent[v]
            idx = parent_edge[v]
            e = self.adj[u][idx]
            e[2] += push
            rev_idx = e[4]
            self.adj[v][rev_idx][2] -= push
            v = u

        return push, push * dist[t]

    def mcmf(self, s, t, max_flow=10**18):
        total_flow = 0
        total_cost = 0
        while True:
            f, c = self.spfa(s, t, total_flow, max_flow)
            if f == 0:
                break
            total_flow += f
            total_cost += c
        return total_flow, total_cost

n, m = map(int, input().split())
mcmf = MinCostMaxFlow(n)
for _ in range(m):
    u, v, cap, cost = map(int, input().split())
    mcmf.add_edge(u, v, cap, cost)
flow, cost = mcmf.mcmf(1, n)
print(flow, cost)

6. Ứng dụng¶

6.1 Khớp đôi đồ thị hai phía (Bipartite Matching)¶

Cho đồ thị hai phía \(G = (U, V, E)\). Tìm tập cạnh đối lớn nhất.

Giả bài toán về max-flow:

Tạo đỉnh nguồn \(s\), nối đến mọi đỉnh trong \(U\) với dung lượng 1
Nối cạnh từ \(U\) đến \(V\) theo đồ thị gốc với dung lượng 1
Nối mọi đỉnh trong \(V\) đến bể \(t\) với dung lượng 1
Chạy max-flow → kết quả = kích thước khớp đôi lớn nhất

graph LR
    s((s)) -->|1| u1((u1))
    s((s)) -->|1| u2((u2))
    s((s)) -->|1| u3((u3))
    u1 -->|1| v1((v1))
    u1 -->|1| v2((v2))
    u2 -->|1| v1
    u3 -->|1| v2
    u3 -->|1| v3((v3))
    v1 -->|1| t((t))
    v2 -->|1| t
    v3 -->|1| t

Max-flow = 3 → Khớp đôi lớn nhất có 3 cặp.

Độ phức tạp: \(O(E\sqrt{V})\) nhờ tính chất đồ thị hai phía của Dinic.

6.2 Định lý König — Đỉnh bao nhỏ nhất¶

Định lý König: Trong đồ thị hai phía, kích thước đỉnh bao nhỏ nhất = kích thước khớp đôi lớn nhất.

Tìm đỉnh bao nhỏ nhất từ max-flow:

Chạy max-flow trên đồ thị hai phía
Dùng BFS từ \(s\) trong đồ thị dư, đánh dấu đỉnh reachable
Đỉnh bao = \((U \setminus \text{reachable}) \cup (V \cap \text{reachable})\)

6.3 Tập độc lập lớn nhất trong đồ thị hai phía¶

Tập độc lập lớn nhất = \(|V| -\) đỉnh bao nhỏ nhất = \(|V| -\) khớp đôi lớn nhất.

6.4 Đường đi cạnh không chung (Edge-Disjoint Paths)¶

Tìm số đường đi từ \(s\) đến \(t\) sao cho không cạnh nào được dùng quá một lần.

Giải: Cho mỗi cạnh dung lượng 1, chạy max-flow. Kết quả = số đường đi cạnh không chung.

6.5 Truy vết cắt nhỏ nhất (Min Cut)¶

Sau khi chạy max-flow, dùng BFS/DFS từ \(s\) trong đồ thị dư. Các đỉnh reachable thuộc tập \(S\), còn lại thuộc tập \(T\). Cạnh cắt là các cạnh từ \(S\) sang \(T\) trong đồ thị gốc mà đã đầy (\(f = c\)).

Hàm minCut() trong cài đặt Dinic ở mục 4 thực hiện chính xác việc này.

7. Lưu ý & Cạm bẫy¶

7.1 Quên cạnh ngược trong đồ thị dư¶

addEdge(u, v, cap) phải tạo cả cạnh \(u \to v\) (dung lượng \(cap\)) lẫn cạnh \(v \to u\) (dung lượng 0). Nếu quên cạnh ngược, thuật toán không thể "rút" luồng đã đẩy sai → sai kết quả!

7.2 Tràn số nguyên với dung lượng lớn¶

Dung lượng có thể lên đến \(10^9\), tổng luồng có thể lên đến \(10^{14}\). Bắt buộc dùng long long (int64), không dùng int!

7.3 MCMF với chu trình âm¶

Nếu đồ thị có chu trình âm trong chi phí, SPFA sẽ bị kẹt trong vòng lặp vô hạn. Đảm bảo đồ thị không có chu trình âm, hoặc dùng Bellman-Ford lần đầu để phát hiện.

7.4 Đồ thị có cạnh song song¶

Nhiều cạnh cùng chiều giữa hai đỉnh → không vấn đề, chỉ cần thêm tất cả vào danh sách cạnh.

7.5 Self-loop¶

Cạnh từ đỉnh về chính mình → có thể bỏ qua, không ảnh hưởng kết quả.

7.6 Đồ thị vô hướng¶

Cạnh vô hướng \((u,v)\) với dung lượng \(c\) tương đương hai cạnh có hướng \((u,v)\) và \((v,u)\) cùng dung lượng \(c\). Gọi addEdge(u, v, cap) và addEdge(v, u, cap).

8. Bài tập luyện tập (FPTOJ)¶

Bài	Nền tảng	Độ khó	Kiểu bài tập (Bản chất)
`flow-max-flow`	Luồng Cực Đại Cơ Bản	⭐⭐⭐	Max flow - Edmonds-Karp
`flow-dinic`	Luồng Cực Đại Dinic	⭐⭐⭐	Max flow - Dinic
`flow-min-cut`	Lát Cắt Cực Tiểu	⭐⭐⭐⭐	Min cut
`flow-bipartite`	Ghép Cặp Hai Phía	⭐⭐⭐	Bipartite matching
`flow-edge-disc`	Cạnh Quan Trọng	⭐⭐⭐⭐	Cạnh tới hạn
`flow-multi-src`	Luồng Đa Nguồn Đích	⭐⭐⭐⭐	Đa nguồn/đa đích
`flow-node-cap`	Dung Lượng Trên Đỉnh	⭐⭐⭐⭐	Chia đỉnh
`flow-max-closure`	Tập Đóng Trọng Số Lớn Nhất	⭐⭐⭐⭐	Max weight closure

Gợi ý giải:

CSES Download Speed: Bài mẫu max-flow. Cài Dinic hoặc Edmonds-Karp, chạy trực tiếp.
CSES Police Chase: Chạy max-flow, rồi dùng BFS trên đồ thị dư để tìm cắt nhỏ nhất.
CSES School Dance: Giả bài về bipartite matching → max-flow.
SPOJ FASTFLOW: Dung lượng lớn → bắt buộc dùng Dinic (Edmonds-Karp sẽ TLE).
SPOJ MATCHING: Đồ thị hai phía lớn → Dinic chạy \(O(E\sqrt{V})\).
CF 277E: Xây đồ thị, gán chi phí cho cạnh, chạy MCMF.

Tóm tắt¶

Thuật toán	Độ phức tạp	Khi nào dùng
Edmonds-Karp	\(O(VE^2)\)	Đồ thị nhỏ, dễ cài
Dinic	\(O(V^2 E)\)	Hầu hết bài max-flow
Dinic (bipartite)	\(O(E\sqrt{V})\)	Khớp đôi đồ thị hai phía
MCMF (SPFA)	\(O(F \cdot VE)\)	Luồng chi phí nhỏ nhất
MCMF (Dijkstra)	\(O(F \cdot E \log V)\)	MCMF đồ thị lớn

Hãy học thuộc cài đặt Dinic. Đây là thuật toán luồng phổ biến nhất trong competitive programming. Khi gặp bài liên quan đến flow, hãy nghĩ đến việc mô hình hóa bài toán thành mạng luồng trước!

Bài 41: Network Flow — Luồng Cực Đại¶

1. Bài toán luồng cực đại¶

Bản chất vấn đề¶

Tư duy cốt lõi¶

2. Ford-Fulkerson & Đồ thị dư¶

Bản chất vấn đề¶

Tư duy cốt lõi¶

Đồ thị dư (Residual Graph)¶

Ví dụ minh họa¶

Phân tích tính đúng đắn¶

Đánh giá độ phức tạp¶

3. Edmonds-Karp (BFS)¶

Bản chất vấn đề¶

Tư duy cốt lõi¶

Phân tích tính đúng đắn¶

Đánh giá độ phức tạp¶

Cài đặt¶

4. Dinic's Algorithm¶

Bản chất vấn đề¶

Tư duy cốt lõi¶

Phân tích tính đúng đắn¶

Đánh giá độ phức tạp¶

Cài đặt¶

5. Min-Cost Max-Flow¶

Bản chất vấn đề¶

Tư duy cốt lõi¶

Phân tích tính đúng đắn¶

Đánh giá độ phức tạp¶

Cài đặt¶

6. Ứng dụng¶

6.1 Khớp đôi đồ thị hai phía (Bipartite Matching)¶

6.2 Định lý König — Đỉnh bao nhỏ nhất¶

6.3 Tập độc lập lớn nhất trong đồ thị hai phía¶

6.4 Đường đi cạnh không chung (Edge-Disjoint Paths)¶

6.5 Truy vết cắt nhỏ nhất (Min Cut)¶

7. Lưu ý & Cạm bẫy¶

7.1 Quên cạnh ngược trong đồ thị dư¶

7.2 Tràn số nguyên với dung lượng lớn¶

7.3 MCMF với chu trình âm¶

7.4 Đồ thị có cạnh song song¶

7.5 Self-loop¶

7.6 Đồ thị vô hướng¶

8. Bài tập luyện tập (FPTOJ)¶

Tóm tắt¶

💬 Bình luận