Maximum Flow

IMạng, luồng và cách tham lam

Một mạng (network) là một đồ thị có hướng, trong đó mỗi cung $u \to v$ có một sức chứa $c(u, v) \ge 0$, và có hai đỉnh đặc biệt: nguồn $s$ và đích $t$. Ta gọi số đỉnh là $V$ và số cung là $E$.

Một luồng (flow) gán cho mỗi cung $u \to v$ một lượng $f(u, v)$, gọi là luồng trên cung đó, thỏa hai điều kiện:

• luồng trên mỗi cung không âm và không vượt quá sức chứa: $0 \le f(u, v) \le c(u, v)$;
• ở mỗi đỉnh khác $s$ và $t$, tổng luồng đi vào bằng tổng luồng đi ra: hàng không tự sinh ra, cũng không mất đi ở giữa đường.

Giá trị của luồng là tổng luồng đi ra khỏi $s$ trừ tổng luồng đi vào $s$, cũng bằng lượng hàng tới được $t$. Bài toán luồng cực đại là tìm một luồng có giá trị lớn nhất.

Hình dưới là một mạng bốn đỉnh, mọi cung có sức chứa $1$, với nguồn là đỉnh $1$ và đích là đỉnh $4$. Luồng trong hình chở $1$ đơn vị theo đường $1 \to 2 \to 4$ và $1$ đơn vị theo đường $1 \to 3 \to 4$, nên có giá trị $2$. Đây cũng là giá trị lớn nhất, vì hai cung đi ra khỏi đỉnh $1$ chỉ chở được tổng cộng $2$ đơn vị.

Cách dễ nghĩ ra nhất là tham lam: tìm một đường đi từ $s$ tới $t$ mà mọi cung trên đường còn chở thêm được, đẩy thêm theo đường đó một lượng bằng sức chứa còn lại nhỏ nhất trên đường, rồi lặp lại cho tới khi không còn đường nào. Câu hỏi dưới đây thử cách này trên chính mạng ở hình trên.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 105;
ll n, m, s, t, cap[N][N], vis[N];

ll dfs(ll u, ll f) {
    if (u == t) return f;
    vis[u] = 1;
    for (ll v = 1; v <= n; v++)
        if (cap[u][v] > 0 && !vis[v]) {
            ll d = dfs(v, min(f, cap[u][v]));
            if (d > 0) {
                cap[u][v] -= d;
                return d;
            }
        }
    return 0;
}

signed main() {
    cin >> n >> m >> s >> t;
    for (ll i = 1; i <= m; i++) {
        ll u, v, c;
        cin >> u >> v >> c;
        cap[u][v] += c;
    }
    ll flow = 0, f;
    do {
        for (ll i = 1; i <= n; i++) vis[i] = 0;
        f = dfs(s, 1e18);
        flow += f;
    } while (f > 0);
    cout << flow << '\n';
}

ChạyInput4 5 1 4
1 2 1
1 3 1
2 3 1
2 4 1
3 4 1

Output1

IICung ngược và Ford-Fulkerson

Ví dụ trên cho thấy cách tham lam có thể đẩy luồng theo hướng không tốt rồi bị kẹt. Cách sửa là cho phép rút lại luồng đã đẩy: nếu cung $u \to v$ đang chở $f$ đơn vị, ta coi như có thêm một cung $v \to u$ chở được $f$ đơn vị. Đẩy hàng theo cung $v \to u$ này nghĩa là giảm bớt luồng trên cung $u \to v$.

Với một luồng đang có, đồ thị dư (residual graph) gồm các cung sau:

• với mỗi cung $u \to v$ của mạng, một cung $u \to v$ có sức chứa $c(u, v) - f(u, v)$, là lượng còn đẩy thêm được;
• và một cung ngược $v \to u$ có sức chứa $f(u, v)$, là lượng có thể rút lại.

Cung nào có sức chứa $0$ thì coi như không có. Một đường tăng luồng (augmenting path) là một đường đi từ $s$ tới $t$ trong đồ thị dư. Đẩy thêm theo đường tăng luồng một lượng bằng sức chứa nhỏ nhất trên đường, giá trị luồng tăng đúng chừng ấy.

Quay lại mạng bốn đỉnh. Sau khi đẩy $1$ đơn vị theo đường $1 \to 2 \to 3 \to 4$, đồ thị dư có cung ngược $3 \to 2$. Nhờ cung này, ta tìm được đường tăng luồng $1 \to 3 \to 2 \to 4$: đẩy theo nó thì luồng trên cung $2 \to 3$ được rút về $0$, phần hàng đi tới đỉnh $2$ chuyển sang cung $2 \to 4$, và luồng tăng lên $2$.

Ford-Fulkerson chính là cách tham lam ở trên, nhưng tìm đường trong đồ thị dư: lặp lại việc tìm một đường tăng luồng bất kỳ và đẩy theo nó, cho tới khi không còn đường tăng luồng. Khi lưu sức chứa bằng ma trận, cung ngược $v \to u$ chính là ô cap[v][u], nên chỉ cần thêm đúng một dòng vào hàm dfs của chương trình trong câu hỏi trên; phần còn lại giữ nguyên:

ll dfs(ll u, ll f) {
    if (u == t) return f;
    vis[u] = 1;
    for (ll v = 1; v <= n; v++)
        if (cap[u][v] > 0 && !vis[v]) {
            ll d = dfs(v, min(f, cap[u][v]));
            if (d > 0) {
                cap[u][v] -= d;
                cap[v][u] += d;
                return d;
            }
        }
    return 0;
}

Độ phức tạp: mỗi lần tìm đường tốn $O(V^2)$ với ma trận, và mỗi lần đẩy thêm ít nhất $1$ đơn vị khi các sức chứa là số nguyên, nên cả thuật toán tốn $O(F \cdot V^2)$, với $F$ là giá trị luồng cực đại.

Khi không còn đường tăng luồng, luồng đang có là luồng cực đại. Điều này không hiển nhiên: có thể nào luồng chưa cực đại mà đã hết đường tăng? Câu trả lời là không (xem ô Chứng minh). Chứng minh dùng một khái niệm quan trọng: một lát cắt (cut) là một cách chia các đỉnh thành hai phần, phần $S$ chứa $s$ và phần $T$ chứa $t$; sức chứa của lát cắt là tổng sức chứa các cung đi từ $S$ sang $T$.

Ford-Fulkerson có thể chạy rất chậm khi giá trị luồng lớn. Trên mạng ở hình dưới, luồng cực đại là $2 \cdot 10^9$. Nếu không may, các đường tăng luồng cứ lần lượt đi qua cung giữa theo hai chiều, $s \to a \to b \to t$ rồi $s \to b \to a \to t$, mỗi lần chỉ tăng được $1$, và thuật toán cần tới $2 \cdot 10^9$ lần tìm đường.

IIIĐường tăng ngắn nhất: Edmonds-Karp

Edmonds-Karp sửa điểm yếu trên bằng một thay đổi nhỏ: luôn chọn đường tăng luồng ngắn nhất, tức là đi qua ít cung nhất, tìm bằng BFS thay vì DFS. Khi đó số lần tăng luồng không quá $O(VE)$, không còn phụ thuộc vào giá trị luồng (xem ô Chứng minh). Trên mạng ở hình trên, hai đường ngắn nhất $s \to a \to t$ và $s \to b \to t$ được chọn trước, và thuật toán xong sau đúng hai lần tăng.

Trong code, BFS ghi lại đỉnh đứng trước của mỗi đỉnh trên đường đi; tới được $t$ thì đi ngược từ $t$ về $s$ hai lượt: lượt đầu tìm sức chứa nhỏ nhất trên đường, lượt sau đẩy luồng. Hàm dưới đây trả về lượng vừa đẩy, hoặc $0$ khi không còn đường tăng luồng; vòng lặp chính gọi nó cho tới khi nhận về $0$.

ll bfs() {
    for (ll i = 1; i <= n; i++) par[i] = 0;
    queue<ll> q;
    q.push(s);
    par[s] = s;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v = 1; v <= n; v++)
            if (cap[u][v] > 0 && !par[v]) {
                par[v] = u;
                q.push(v);
            }
    }
    if (!par[t]) return 0;
    ll d = 1e18;
    for (ll v = t; v != s; v = par[v]) d = min(d, cap[par[v]][v]);
    for (ll v = t; v != s; v = par[v]) {
        cap[par[v]][v] -= d;
        cap[v][par[v]] += d;
    }
    return d;
}

Độ phức tạp: mỗi lần BFS trên ma trận tốn $O(V^2)$ và có không quá $O(VE)$ lần tăng luồng, nên cả thuật toán tốn $O(V^3 E)$; nếu lưu đồ thị bằng danh sách cạnh như ở mục sau, mỗi lần BFS chỉ tốn $O(E)$ và cả thuật toán tốn $O(VE^2)$. Trong thực tế, số lần tăng luồng thường ít hơn cận này rất nhiều.

IVTăng luồng theo từng pha: Dinic

Edmonds-Karp mỗi lần BFS chỉ dùng được một đường. Ta có thể thấy được điểm lãng phí: thường có nhiều đường tăng luồng cùng ngắn nhất, nhưng mỗi đường lại cần một lần BFS riêng. Dinic dùng một lần BFS cho tất cả các đường ngắn nhất cùng độ dài.

Dinic chạy theo từng pha. Đầu mỗi pha, BFS từ $s$ trong đồ thị dư để tính mức của mỗi đỉnh, là khoảng cách từ $s$ tới đỉnh đó. Trong pha này, ta chỉ dùng những cung đi từ một đỉnh ở mức $d$ tới một đỉnh ở mức $d + 1$; mọi đường từ $s$ tới $t$ chỉ đi theo các cung này đều là đường ngắn nhất. Sau đó DFS đẩy luồng theo các đường như vậy, hết đường này tới đường khác, cho tới khi không còn đường nào. Hết pha, ta BFS lại để bắt đầu pha mới; khi BFS không tới được $t$ nữa thì luồng đã cực đại.

Để DFS không thử đi thử lại những cung vô ích, mỗi đỉnh $u$ giữ một con trỏ cung: chỉ số của cung đầu tiên đáng thử. Một cung đã hết sức chứa, hay dẫn tới một đỉnh không còn đường tới $t$, thì con trỏ bỏ qua nó luôn cho tới hết pha.

Với đồ thị lớn, ma trận kề tốn $V^2$ ô nhớ và mỗi lần duyệt các đỉnh kề tốn $O(V)$. Vì vậy từ đây ta lưu đồ thị bằng danh sách cạnh: các cung được đánh số $0, 1, 2, \dots$, mỗi cung lưu đỉnh cuối và sức chứa dư, và mỗi đỉnh giữ danh sách số hiệu các cung đi ra. Khi thêm cung $u \to v$, ta thêm luôn cung ngược $v \to u$ với sức chứa $0$ ngay sau nó. Hai cung một cặp mang số hiệu $2k$ và $2k + 1$, nên cung ngược của cung $e$ là cung $e \oplus 1$, viết trong C++ là e ^ 1.

Trong mô phỏng dưới đây, mỗi pha bắt đầu bằng BFS ghi mức lên các đỉnh, rồi đẩy luồng theo các đường cam; nhãn mỗi cung là luồng trên sức chứa. Bước cuối tô lát cắt nhỏ nhất, sẽ nói ở mục sau.

Ví dụBăng Thông Cực Đại

Đề. Có $n \le 500$ máy tính và $m \le 1000$ kết nối một chiều, mỗi kết nối có băng thông không quá $10^9$. Tìm tốc độ truyền dữ liệu lớn nhất từ máy $1$ tới máy $n$.

Lời giải. Đây đúng là bài toán luồng cực đại từ đỉnh $1$ tới đỉnh $n$. Trong code, to[e] và cap[e] là đỉnh cuối và sức chứa dư của cung $e$, g[u] là danh sách cung đi ra từ $u$, lv[u] là mức của đỉnh $u$, và it[u] là con trỏ cung của $u$. Mỗi pha gọi bfs để tính mức, đặt lại con trỏ cung, rồi gọi dfs liên tiếp cho tới khi nó trả về $0$. Nhiều kết nối giữa cùng hai máy chỉ là các cung song song, không cần gộp. Luồng có thể tới $1000 \cdot 10^9 = 10^{12}$, nên cần dùng kiểu long long.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 505, M = 2005, INF = 4e18;
ll n, m, ec, to[M], cap[M], lv[N], it[N];
vector<ll> g[N];

void addEdge(ll u, ll v, ll c) {
    to[ec] = v, cap[ec] = c, g[u].push_back(ec++);
    to[ec] = u, cap[ec] = 0, g[v].push_back(ec++);
}

bool bfs(ll s, ll t) {
    for (ll i = 0; i <= n; i++) lv[i] = -1;
    queue<ll> q;
    q.push(s);
    lv[s] = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll e : g[u])
            if (cap[e] > 0 && lv[to[e]] < 0) {
                lv[to[e]] = lv[u] + 1;
                q.push(to[e]);
            }
    }
    return lv[t] >= 0;
}

ll dfs(ll u, ll t, ll f) {
    if (u == t) return f;
    for (; it[u] < (ll)g[u].size(); it[u]++) {
        ll e = g[u][it[u]], v = to[e];
        if (cap[e] > 0 && lv[v] == lv[u] + 1) {
            ll d = dfs(v, t, min(f, cap[e]));
            if (d > 0) {
                cap[e] -= d;
                cap[e ^ 1] += d;
                return d;
            }
        }
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        addEdge(a, b, c);
    }
    ll flow = 0;
    while (bfs(1, n)) {
        for (ll i = 0; i <= n; i++) it[i] = 0;
        ll f;
        while ((f = dfs(1, n, INF)) > 0) flow += f;
    }
    cout << flow << '\n';
}

ChạyInput5 7
1 2 4
1 3 7
2 4 3
3 2 2
3 4 4
4 5 6
2 5 1

Output7

Độ phức tạp: $O(V^2 E)$ trong trường hợp xấu nhất; với $V = 500$ và $E = 2000$ cung (tính cả cung ngược), cận này là $5 \cdot 10^8$, nhưng thực tế Dinic chạy nhanh hơn cận này rất nhiều.

Nếu bỏ con trỏ cung, chương trình vẫn đúng nhưng chậm hơn: mỗi lần dfs lại thử lại từ đầu mọi cung đã vô ích. Hình dưới đo trên một mạng ghép cặp lớn:

Chỉ thêm một mảng con trỏ mà chương trình nhanh hơn khoảng $13$ lần, và chênh lệch thường càng lớn khi đồ thị càng dày.

VLát cắt nhỏ nhất

Nhắc lại, một lát cắt chia các đỉnh thành phần $S$ chứa $s$ và phần $T$ chứa $t$, và sức chứa của lát cắt là tổng sức chứa các cung từ $S$ sang $T$. Bài toán lát cắt nhỏ nhất (minimum cut) là tìm lát cắt có sức chứa nhỏ nhất. Nói cách khác: xóa các cung có tổng sức chứa nhỏ nhất để không còn đường đi từ $s$ tới $t$.

Ô Chứng minh ở mục Cung ngược và Ford-Fulkerson đã cho ta một kết quả quan trọng, gọi là định lý luồng cực đại bằng lát cắt nhỏ nhất: giá trị luồng cực đại đúng bằng sức chứa của lát cắt nhỏ nhất. Chứng minh đó cũng cho cách tìm lát cắt: chạy luồng cực đại xong, BFS thêm một lần từ $s$ trong đồ thị dư; các đỉnh tới được là phần $S$, và các cung từ $S$ sang $T$ là các cung cần xóa.

Bài “xóa ít cạnh nhất để tách $s$ khỏi $t$” là bài lát cắt nhỏ nhất với sức chứa $1$ cho mỗi cạnh. Với đồ thị vô hướng, mỗi cạnh $u$, $v$ được thay bằng hai cung $u \to v$ và $v \to u$ cùng sức chứa $1$. Trong cài đặt bằng danh sách cạnh, ta chỉ cần một cặp cung số hiệu $2k$ và $2k + 1$, cả hai đều có sức chứa $1$: cặp cung này vừa là hai chiều của cạnh, vừa là cung ngược của nhau.

Sử dụng kiến thức này cũng có thể giải bài: ngoài việc xóa cạnh, được phép tắt một số đỉnh đặc biệt để chúng không còn nhận hàng, nhưng hàng vẫn đi qua chúng được. Thêm một đích chung, nối mỗi đỉnh đặc biệt tới đích chung bằng một cung sức chứa $1$; cắt cung đó nghĩa là tắt đỉnh đó.

Ví dụChốt Chặn Tối Thiểu

Đề. Cho đồ thị vô hướng $n \le 500$ đỉnh, $m \le 1000$ cạnh. Đóng ít cạnh nhất để không còn đường đi giữa đỉnh $1$ và đỉnh $n$; in số cạnh cần đóng và các cạnh đó.

Lời giải. Đây là bài lát cắt nhỏ nhất với sức chứa $1$ cho mỗi cạnh, nên số cạnh cần đóng bằng luồng cực đại. Mỗi cạnh là một cặp cung cùng sức chứa $1$ như trên. Chạy Dinic xong, gọi bfs(1, n) thêm một lần: lúc này không tới được $n$, nhưng các đỉnh có lv[v] >= 0 chính là các đỉnh tới được từ $1$, tức là phần $S$. Cạnh có đúng một đầu thuộc $S$ là cạnh cần đóng; theo câu hỏi trên, các cạnh này đều đầy theo chiều từ $S$ sang $T$, nên số cạnh đúng bằng luồng.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 505, M = 2005, INF = 4e18;
ll n, m, ec, to[M], cap[M], lv[N], it[N], ea[M], eb[M];
vector<ll> g[N];

bool bfs(ll s, ll t) {
    for (ll i = 0; i <= n; i++) lv[i] = -1;
    queue<ll> q;
    q.push(s);
    lv[s] = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll e : g[u])
            if (cap[e] > 0 && lv[to[e]] < 0) {
                lv[to[e]] = lv[u] + 1;
                q.push(to[e]);
            }
    }
    return lv[t] >= 0;
}

ll dfs(ll u, ll t, ll f) {
    if (u == t) return f;
    for (; it[u] < (ll)g[u].size(); it[u]++) {
        ll e = g[u][it[u]], v = to[e];
        if (cap[e] > 0 && lv[v] == lv[u] + 1) {
            ll d = dfs(v, t, min(f, cap[e]));
            if (d > 0) {
                cap[e] -= d;
                cap[e ^ 1] += d;
                return d;
            }
        }
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> ea[i] >> eb[i];
        to[ec] = eb[i], cap[ec] = 1, g[ea[i]].push_back(ec++);
        to[ec] = ea[i], cap[ec] = 1, g[eb[i]].push_back(ec++);
    }
    ll flow = 0;
    while (bfs(1, n)) {
        for (ll i = 0; i <= n; i++) it[i] = 0;
        ll f;
        while ((f = dfs(1, n, INF)) > 0) flow += f;
    }
    bfs(1, n);
    cout << flow << '\n';
    for (ll i = 1; i <= m; i++)
        if ((lv[ea[i]] >= 0) != (lv[eb[i]] >= 0)) cout << ea[i] << ' ' << eb[i] << '\n';
}

ChạyInput6 8
1 2
1 3
2 4
3 4
2 5
3 5
4 6
5 6

Output2
1 2
1 3

Độ phức tạp: luồng không quá $m$, mỗi pha tốn $O(m)$ khi mọi sức chứa bằng $1$, và số pha cũng nhỏ; với $m = 1000$ chương trình chạy rất nhanh, cỡ $O(m \sqrt{m}) \approx 3 \cdot 10^4$ bước.

VIGhép cặp hai phía

Bài toán: có hai nhóm đỉnh $A$ và $B$, và một số cạnh nối một đỉnh của $A$ với một đỉnh của $B$. Chọn nhiều cạnh nhất sao cho không có hai cạnh được chọn nào chung đỉnh. Các cạnh được chọn gọi là một cặp ghép (matching).

Ta dựng một mạng: thêm nguồn $s$ nối tới mọi đỉnh của $A$ bằng cung sức chứa $1$; mọi đỉnh của $B$ nối tới đích $t$ bằng cung sức chứa $1$; mỗi cạnh giữa $A$ và $B$ thành cung từ $A$ sang $B$ sức chứa $1$. Mỗi đỉnh của $A$ nhận nhiều nhất $1$ đơn vị từ nguồn, mỗi đỉnh của $B$ gửi nhiều nhất $1$ đơn vị tới đích, nên mỗi luồng mà luồng trên mọi cung là số nguyên ứng với đúng một cặp ghép: cặp ghép gồm các cung từ $A$ sang $B$ có luồng $1$. Khi mọi sức chứa là số nguyên, Ford-Fulkerson, Edmonds-Karp và Dinic đều cho luồng như vậy, vì mỗi lần đẩy chỉ cộng trừ các số nguyên.

Trên mạng ghép cặp, Dinic chạy trong $O(E \sqrt{V})$, nhanh hơn nhiều so với cận chung $O(V^2 E)$.

Ví dụGhép Đôi Sân Khấu

Đề. Có $n \le 500$ người ở nhóm thứ nhất, $m \le 500$ người ở nhóm thứ hai, và $k \le 1000$ cặp hợp lệ, mỗi cặp gồm một người mỗi nhóm. Chọn nhiều cặp nhất, mỗi người thuộc nhiều nhất một cặp, và in các cặp được chọn.

Lời giải. Dựng mạng ghép cặp như trên. Đánh số: nguồn là đỉnh $0$, nhóm thứ nhất là các đỉnh $1$ tới $n$, nhóm thứ hai là các đỉnh $n + 1$ tới $n + m$, đích là đỉnh $n + m + 1$. Hàm addEdge trả về số hiệu cung vừa thêm, và mảng eid giữ số hiệu cung của từng cặp hợp lệ. Chạy Dinic xong, cung của một cặp hết sức chứa nghĩa là có luồng $1$ đi qua, tức là cặp đó được chọn. Nếu một cặp xuất hiện hai lần trong dữ liệu, ta có hai cung song song, nhưng nhiều nhất một cung được dùng, vì mỗi người ở nhóm thứ nhất chỉ nhận $1$ đơn vị từ nguồn.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1005, M = 6005, INF = 4e18;
ll n, m, k, V, ec, to[M], cap[M], lv[N], it[N], ea[M], eb[M], eid[M];
vector<ll> g[N];

bool bfs(ll s, ll t) {
    for (ll i = 0; i <= V; i++) lv[i] = -1;
    queue<ll> q;
    q.push(s);
    lv[s] = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll e : g[u])
            if (cap[e] > 0 && lv[to[e]] < 0) {
                lv[to[e]] = lv[u] + 1;
                q.push(to[e]);
            }
    }
    return lv[t] >= 0;
}

ll dfs(ll u, ll t, ll f) {
    if (u == t) return f;
    for (; it[u] < (ll)g[u].size(); it[u]++) {
        ll e = g[u][it[u]], v = to[e];
        if (cap[e] > 0 && lv[v] == lv[u] + 1) {
            ll d = dfs(v, t, min(f, cap[e]));
            if (d > 0) {
                cap[e] -= d;
                cap[e ^ 1] += d;
                return d;
            }
        }
    }
    return 0;
}

ll addEdge(ll u, ll v, ll c) {
    to[ec] = v, cap[ec] = c, g[u].push_back(ec++);
    to[ec] = u, cap[ec] = 0, g[v].push_back(ec++);
    return ec - 2;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    V = n + m + 1;
    for (ll i = 1; i <= k; i++) {
        cin >> ea[i] >> eb[i];
        eid[i] = addEdge(ea[i], n + eb[i], 1);
    }
    for (ll i = 1; i <= n; i++) addEdge(0, i, 1);
    for (ll j = 1; j <= m; j++) addEdge(n + j, V, 1);
    ll flow = 0;
    while (bfs(0, V)) {
        for (ll i = 0; i <= V; i++) it[i] = 0;
        ll f;
        while ((f = dfs(0, V, INF)) > 0) flow += f;
    }
    cout << flow << '\n';
    for (ll i = 1; i <= k; i++)
        if (cap[eid[i]] == 0) cout << ea[i] << ' ' << eb[i] << '\n';
}

ChạyInput4 3 7
1 1
1 2
2 1
2 3
3 2
4 2
4 3

Output3
1 1
2 3
3 2

Độ phức tạp: $O(E \sqrt{V})$ trên mạng ghép cặp; với $V \approx 1000$ đỉnh và $E \approx 2000$ cung, cần cỡ $6 \cdot 10^4$ bước.

VIIChọn dự án

Bài toán: có một số dự án, mỗi dự án mang lại một khoản lợi nhuận, và một số công cụ, mỗi công cụ tốn một khoản chi phí. Mỗi dự án cần một số công cụ: chọn làm dự án thì phải mua đủ các công cụ nó cần. Chọn các dự án và công cụ để tổng lợi nhuận trừ tổng chi phí lớn nhất.

Dựng mạng như sau:

• nguồn $s$ nối tới mỗi dự án bằng cung có sức chứa bằng lợi nhuận của dự án;
• mỗi công cụ nối tới đích $t$ bằng cung có sức chứa bằng chi phí của công cụ;
• nếu dự án $x$ cần công cụ $y$, thêm cung $x \to y$ có sức chứa vô hạn, trong code là một số rất lớn.

Với một lát cắt $(S, T)$ có sức chứa hữu hạn, ta chọn các dự án và công cụ thuộc phần $S$. Đáp án là tổng lợi nhuận của mọi dự án trừ đi sức chứa của lát cắt nhỏ nhất (xem ô Chứng minh).

Ví dụChọn Dự Án Trên Đồ Thị

Đề. Cho đồ thị $n \le 1000$ đỉnh, đỉnh thứ $i$ có chi phí $a_i$, và $m \le 1000$ cạnh, mỗi cạnh có trọng số $w$. Chọn một số cạnh; chọn cạnh nào thì phải chọn cả hai đầu mút của nó. Giá trị là tổng trọng số các cạnh được chọn trừ tổng chi phí các đỉnh được chọn. Tìm giá trị lớn nhất.

Lời giải. Mỗi cạnh là một dự án với lợi nhuận $w$, mỗi đỉnh là một công cụ với chi phí $a_i$, và mỗi cạnh cần hai đầu mút của nó. Đánh số: nguồn là đỉnh $0$, các cạnh là đỉnh $1$ tới $m$, các đỉnh của đồ thị là đỉnh $m + 1$ tới $m + n$, đích là đỉnh $m + n + 1$. Đáp án là tổng trọng số mọi cạnh trừ đi luồng cực đại. Sức chứa vô hạn đặt bằng $4 \cdot 10^{18}$, lớn hơn hẳn mọi lát cắt hữu hạn (tổng trọng số không quá $10^{12}$), và vì hàm dfs luôn lấy min với sức chứa thật nên không bị tràn số. Không chọn cạnh nào thì giá trị là $0$, nên đáp án không bao giờ âm.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2005, M = 10005, INF = 4e18;
ll n, m, V, ec, to[M], cap[M], lv[N], it[N];
vector<ll> g[N];

void addEdge(ll u, ll v, ll c) {
    to[ec] = v, cap[ec] = c, g[u].push_back(ec++);
    to[ec] = u, cap[ec] = 0, g[v].push_back(ec++);
}

bool bfs(ll s, ll t) {
    for (ll i = 0; i <= V; i++) lv[i] = -1;
    queue<ll> q;
    q.push(s);
    lv[s] = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll e : g[u])
            if (cap[e] > 0 && lv[to[e]] < 0) {
                lv[to[e]] = lv[u] + 1;
                q.push(to[e]);
            }
    }
    return lv[t] >= 0;
}

ll dfs(ll u, ll t, ll f) {
    if (u == t) return f;
    for (; it[u] < (ll)g[u].size(); it[u]++) {
        ll e = g[u][it[u]], v = to[e];
        if (cap[e] > 0 && lv[v] == lv[u] + 1) {
            ll d = dfs(v, t, min(f, cap[e]));
            if (d > 0) {
                cap[e] -= d;
                cap[e ^ 1] += d;
                return d;
            }
        }
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    V = n + m + 1;
    for (ll i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        addEdge(m + i, V, a);
    }
    ll sum = 0;
    for (ll i = 1; i <= m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        sum += w;
        addEdge(0, i, w);
        addEdge(i, m + u, INF);
        addEdge(i, m + v, INF);
    }
    ll flow = 0;
    while (bfs(0, V)) {
        for (ll i = 0; i <= V; i++) it[i] = 0;
        ll f;
        while ((f = dfs(0, V, INF)) > 0) flow += f;
    }
    cout << sum - flow << '\n';
}

ChạyInput2 1
3 4
1 2 10

Output3

Độ phức tạp: Dinic trên $n + m + 2 \approx 2000$ đỉnh và $2(3m + n) \approx 8000$ cung; cận $O(V^2 E)$ rất lớn, nhưng thực tế chương trình chạy trong vài mili giây.