Luồng cực đại · Network Flow · Thuật toán Canuc80k

Một mạng là đồ thị có hướng với sức chứa trên mỗi cung, một đỉnh nguồn $s$ và một đỉnh đích $t$ . Luồng gán cho mỗi cung một lượng không vượt sức chứa, với mọi đỉnh trung gian lượng vào bằng lượng ra. Bài toán luồng cực đại tìm luồng lớn nhất đi từ $s$ tới $t$ . Nó quan trọng không chỉ vì chính nó: lát cắt nhỏ nhất, ghép cặp hai phía, đường đi không chung cạnh, chọn tập có lợi nhất với ràng buộc kéo theo đều là luồng cực đại trên một mạng dựng khéo.

Đồ thị dư và thuật toán Dinic

Với một luồng $f$ , đồ thị dư có cung $u \to v$ sức chứa $c - f$ (phần còn đẩy thêm được) và cung ngược $v \to u$ sức chứa $f$ (phần có thể rút lại). Một đường tăng luồng là đường từ $s$ tới $t$ trong đồ thị dư; đẩy thêm theo nó một lượng bằng sức chứa nhỏ nhất trên đường. Cung ngược cho phép “hối hận”: luồng đã đi sai đường được đẩy ngược về để đi đường khác. Luồng là cực đại khi và chỉ khi không còn đường tăng luồng.

Nhãn cạnh là luồng/sức chứa. Mỗi pha BFS cho mức, rồi đẩy theo các đường tăng (cam). Bước cuối tô lát cắt nhỏ nhất.

Dinic làm theo pha. Mỗi pha BFS từ $s$ tính mức (khoảng cách) của mọi đỉnh trong đồ thị dư; chỉ dùng cung đi từ mức $d$ lên mức $d + 1$ . Trên đồ thị phân mức đó, DFS đẩy luồng cho tới khi không còn đường nào (luồng chặn), với con trỏ it[u] nhớ cung đã thử để không thử lại cung đã hết. Có $O(V)$ pha, tổng $O(V^2 E)$ ; trên đồ thị hai phía sức chứa đơn vị chỉ $O(E \sqrt V)$ . Thực tế Dinic chạy nhanh hơn cận này rất nhiều.

Cài bằng danh sách cạnh: cung thứ $e$ và cung ngược của nó là $e$ và $e \oplus 1$ , nên cập nhật một cặp chỉ là cap[e] -= d; cap[e ^ 1] += d.

C++

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;
}

Hỏi nhanh

Vì sao đồ thị dư cần cung ngược với sức chứa bằng luồng đang có?

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

Đề. $n \le 500$ máy, $m \le 1000$ kết nối một chiều có băng thông tới $10^9$ . Tìm tốc độ truyền lớn nhất từ máy 1 tới máy $n$ .

Lời giải. Luồng cực đại từ 1 tới $n$ bằng Dinic. Mỗi pha: BFS từ nguồn trên đồ thị dư để gán mức cho từng đỉnh; rồi DFS chỉ đi theo cung từ mức $\ell$ sang mức $\ell + 1$ , đẩy luồng tới khi không đẩy được nữa. Sau mỗi pha, khoảng cách từ nguồn tới đích trên đồ thị dư tăng ít nhất 1, nên không quá $n$ pha. Kết nối lặp chỉ là cung song song, không cần gộp. Luồng tới $1000 \cdot 10^9 = 10^{12}$ , dùng long long.

Bước 1: cung và cung ngược. Mỗi cung có một cung ngược sức chứa 0 đặt ngay sau nó, nên hai cung là e và e ^ 1. Đẩy d đơn vị qua e thì cap[e] -= d, cap[e ^ 1] += d: cung ngược cho phép “trả lại” luồng ở pha sau.

C++

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++);
}

Bước 2: BFS gán mức. lv là khoảng cách theo số cung, chỉ đi cung còn cap > 0. Trả về đích có tới được hay không.

C++

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;
}

Bước 3: DFS đẩy luồng. dfs(u, t, f) tìm một đường từ u tới đích trên đồ thị mức, mang tối đa f đơn vị, trả về lượng đẩy được. it[u] nhớ cung đang xét của u: cung đã thử mà không đẩy được (bão hòa hoặc dẫn vào ngõ cụt) thì pha này không thử lại, nên mỗi pha tốn $O(VE)$ .

C++

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;
}

Bước 4: các pha. Mỗi pha đặt lại it, rồi gọi dfs liên tiếp tới khi trả 0. INF là luồng mang vào từ nguồn, không giới hạn.

C++

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;
}

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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';
}

Output7

$O(V^2 E)$ trong trường hợp xấu nhất, thực tế nhanh hơn nhiều.

Lát cắt nhỏ nhất

Một lát cắt chia đỉnh thành hai phần $S \ni s$ và $T \ni t$ ; giá trị của nó là tổng sức chứa các cung từ $S$ sang $T$ . Mọi luồng đều phải đi qua lát cắt, nên luồng không vượt lát cắt nào. Định lý luồng cực đại bằng lát cắt nhỏ nhất: khi luồng cực đại, gọi $S$ là các đỉnh tới được từ $s$ trong đồ thị dư; mọi cung từ $S$ sang $T$ đều bão hòa (nếu không, đầu kia đã tới được), mọi cung từ $T$ về $S$ đều rỗng, nên giá trị lát cắt này đúng bằng luồng. Vậy chạy luồng cực đại xong, một lần BFS cho luôn lát cắt nhỏ nhất.

Bài “bỏ ít cạnh nhất để tách $s$ khỏi $t$ ” là lát cắt nhỏ nhất với sức chứa 1 mỗi cạnh. Cạnh vô hướng là hai cung ngược chiều; cài gọn bằng một cặp cung mà cả hai chiều đều có sức chứa 1. “Tắt” một đỉnh đặc biệt cũng là một cạnh để cắt: nối nó tới một đích chung bằng cung sức chứa 1.

Hỏi nhanh

Luồng cực đại vừa chạy xong. Lấy $S$ là các đỉnh tới được từ $s$ trong đồ thị dư. Vì sao lát cắt $(S, T)$ có giá trị đúng bằng luồng?

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

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

Lời giải. Đóng ít cạnh nhất để tách 1 khỏi $n$ là lát cắt nhỏ nhất với sức chứa 1 mỗi cạnh, và giá trị đó bằng luồng cực đại. Khi luồng đã cực đại, các đỉnh còn tới được từ 1 trên đồ thị dư là phía nguồn $S$ ; cạnh có đúng một đầu trong $S$ là cạnh bị cắt. bfs, dfs như ví dụ trước.

Bước 1: cạnh vô hướng. Hai cung ec và ec + 1 đều có cap = 1, đặt liền nhau nên e ^ 1 vẫn là cung ngược của nhau. Đẩy 1 đơn vị theo một chiều thì chiều kia có cap = 2, đúng với việc trả lại luồng cũ rồi đi tiếp chiều ngược.

C++

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++);

Bước 2: tìm phía $S$ . Sau vòng Dinic gọi bfs(1, n) thêm một lần. Lúc này không tới được $n$ , nhưng lv[v] >= 0 vẫn đánh dấu đúng các đỉnh tới được từ 1.

Bước 3: in cạnh cắt. Cạnh có một đầu trong $S$ , một đầu ngoài. Mọi cạnh như vậy đều bão hòa theo chiều từ $S$ ra, nên số của chúng đúng bằng luồng.

C++

for (ll i = 1; i <= m; i++)
    if ((lv[ea[i]] >= 0) != (lv[eb[i]] >= 0)) cout << ea[i] << ' ' << eb[i] << '\n';

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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], vis[N];
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';
}

Output2
1 2
1 3

Luồng không quá $m$ nên Dinic chạy rất nhanh, cỡ $O(E\sqrt{E})$ .

Ví dụKhóa Các Bộ Thu

Đề. Mạng $n \le 100$ trạm, trạm 0 phát tín hiệu, $g$ trạm đặc biệt đang nhận. Mỗi thao tác tắt một liên kết hoặc tắt chức năng nhận của một trạm đặc biệt (tín hiệu vẫn đi qua được). Tìm số thao tác ít nhất để không trạm đặc biệt nào đang nhận còn tới được từ trạm 0.

Lời giải. Hai loại thao tác đều thành “cắt một cung sức chứa 1”. Thêm đỉnh đích $T = n$ (trạm đánh số $0..n-1$ nên không trùng); trạm đặc biệt nối tới $T$ bằng cung sức chứa 1, cắt cung đó là tắt chức năng nhận mà tín hiệu vẫn đi qua trạm được. Mỗi liên kết là cặp cung sức chứa 1 cả hai chiều như ví dụ trước. Không trạm đặc biệt nào còn nhận tín hiệu nghĩa là không còn đường từ 0 tới $T$ , nên đáp án là lát cắt nhỏ nhất, bằng luồng cực đại. bfs, dfs như trên.

Bước 1: một hàm thêm cặp cung. Cung $u \to v$ sức chứa c1, cung ngược sức chứa c2. Trạm đặc biệt dùng (1, 0) vì tín hiệu chỉ đi vào $T$ ; liên kết dùng (1, 1) vì vô hướng.

C++

void addPair(ll u, ll v, ll c1, ll c2) {
    to[ec] = v, cap[ec] = c1, g[u].push_back(ec++);
    to[ec] = u, cap[ec] = c2, g[v].push_back(ec++);
}

C++

addPair(p, n, 1, 0);
addPair(u, v, 1, 1);

Chỉ cần in giá trị luồng.

Code đầy đủ

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

const ll N = 105, M = 20005, INF = 4e18;
ll n, gg, e, ec, to[M], cap[M], lv[N], it[N];
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 x : g[u])
            if (cap[x] > 0 && lv[to[x]] < 0) {
                lv[to[x]] = lv[u] + 1;
                q.push(to[x]);
            }
    }
    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 x = g[u][it[u]], v = to[x];
        if (cap[x] > 0 && lv[v] == lv[u] + 1) {
            ll d = dfs(v, t, min(f, cap[x]));
            if (d > 0) {
                cap[x] -= d;
                cap[x ^ 1] += d;
                return d;
            }
        }
    }
    return 0;
}

void addPair(ll u, ll v, ll c1, ll c2) {
    to[ec] = v, cap[ec] = c1, g[u].push_back(ec++);
    to[ec] = u, cap[ec] = c2, g[v].push_back(ec++);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> gg >> e;
    for (ll i = 1; i <= gg; i++) {
        ll p;
        cin >> p;
        addPair(p, n, 1, 0);
    }
    for (ll i = 1; i <= e; i++) {
        ll u, v;
        cin >> u >> v;
        addPair(u, v, 1, 1);
    }
    ll flow = 0;
    while (bfs(0, n)) {
        for (ll i = 0; i <= n; i++) it[i] = 0;
        ll f;
        while ((f = dfs(0, n, INF)) > 0) flow += f;
    }
    cout << flow << '\n';
}

Output2

Luồng không quá $g$ , mỗi pha $O(E)$ cho đồ thị sức chứa đơn vị.

Ghép cặp hai phía

Đồ thị hai phía $A$ , $B$ : chọn nhiều cạnh nhất sao cho không hai cạnh chung đỉnh. Thêm nguồn 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 bằng cung sức chứa 1, các cạnh $A \to B$ sức chứa 1. Một luồng nguyên tương ứng đúng một cặp ghép: mỗi đỉnh nhận hoặc gửi nhiều nhất 1 đơn vị. Cặp ghép đọc ra từ các cung $A \to B$ đã bão hòa. Dinic trên mạng này chạy trong $O(E \sqrt V)$ , cùng độ phức tạp với Hopcroft-Karp (bài 64).

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

Đề. $n, m \le 500$ người ở hai nhóm, $k \le 1000$ cặp hợp lệ. Chọn nhiều cặp nhất, mỗi người tối đa một cặp, in các cặp.

Lời giải. Mạng ghép cặp: nguồn nối tới mỗi người nhóm $A$ bằng cung sức chứa 1, mỗi người nhóm $B$ nối tới đích bằng cung sức chứa 1, mỗi cặp hợp lệ là cung $A \to B$ sức chứa 1. Luồng nguyên trên mạng này ứng đúng với một cặp ghép, vì mỗi người nhận hay gửi nhiều nhất 1 đơn vị. Đánh số: nguồn 0, nhóm $A$ là $1..n$ , nhóm $B$ là $n + 1..n + m$ , đích $n + m + 1$ . bfs, dfs như trên.

Bước 1: nhớ cung của từng cặp. addEdge trả về chỉ số cung vừa thêm; eid[i] giữ cung của cặp thứ $i$ để đọc lại sau. Thứ tự thêm cung không ảnh hưởng kết quả.

C++

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;
}

C++

eid[i] = addEdge(ea[i], n + eb[i], 1);

Bước 2: đọc cặp ghép. Mọi sức chứa nguyên nên Dinic cho luồng nguyên: mỗi cung $A \to B$ mang 0 hoặc 1, và cap[eid[i]] == 0 là cặp được chọn. Cặp lặp trong input tạo hai cung song song; tối đa một cung được dùng, vì người ở nhóm $A$ chỉ nhận 1 đơn vị từ nguồn.

C++

for (ll i = 1; i <= k; i++)
    if (cap[eid[i]] == 0) cout << ea[i] << ' ' << eb[i] << '\n';

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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';
}

Output3
1 1
2 3
3 2

Dinic trên mạng ghép cặp chạy $O(E\sqrt{V})$ .

Chọn dự án bằng lát cắt

Có các phần tử với lợi nhuận dương hoặc chi phí, và ràng buộc kéo theo: chọn $x$ thì phải chọn $y$ . Tìm tập hợp lệ có tổng lớn nhất. Dựng mạng: nguồn nối tới mỗi phần tử có lợi $p > 0$ bằng cung sức chứa $p$ ; mỗi phần tử có chi phí $c$ nối tới đích bằng cung sức chứa $c$ ; ràng buộc $x \Rightarrow y$ là cung $x \to y$ sức chứa vô hạn. Một lát cắt hữu hạn ứng với tập $S$ (phía nguồn) là tập được chọn, thỏa mọi ràng buộc vì không cung vô hạn nào bị cắt. Giá trị lát cắt là (lợi của phần tử không chọn) cộng (chi phí của phần tử được chọn), nên đáp án là tổng mọi lợi trừ lát cắt nhỏ nhất.

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

Đề. Đồ thị $n \le 1000$ đỉnh có chi phí $a_i$ , $m \le 1000$ cạnh có trọng số $w$ . Chọn một số cạnh (phải chọn cả hai đầu), giá trị là tổng trọng số cạnh trừ tổng chi phí đỉnh đã chọn. Tìm giá trị lớn nhất.

Lời giải. Bài chọn dự án: mỗi cạnh là một dự án lợi $w$ , chọn nó thì phải chọn hai đầu mút; mỗi đỉnh là một khoản chi phí $a_i$ . Dựng mạng: nguồn nối tới mỗi cạnh bằng cung sức chứa $w$ , mỗi đỉnh nối tới đích bằng cung sức chứa $a_i$ , mỗi cạnh nối tới hai đầu mút bằng cung sức chứa vô hạn. Lát cắt hữu hạn không cắt cung vô hạn nào, nên phía nguồn là một lựa chọn hợp lệ; giá trị lát cắt là lợi của các cạnh không chọn cộng chi phí các đỉnh được chọn. Đáp án là $\sum w$ trừ lát cắt nhỏ nhất. Nút: nguồn 0, cạnh $1..m$ , đỉnh $m + 1..m + n$ , đích $m + n + 1$ .

Bước 1: chi phí đỉnh.

C++

addEdge(m + i, V, a);

Bước 2: lợi và ràng buộc của cạnh. Cung từ nguồn mang lợi $w$ ; hai cung INF tới hai đầu mút là ràng buộc “chọn cạnh thì phải chọn đỉnh”.

C++

sum += w;
addEdge(0, i, w);
addEdge(i, m + u, INF);
addEdge(i, m + v, INF);

INF = 4e18 lớn hơn hẳn mọi lát cắt hữu hạn (tổng lợi tới $10^{12}$ ), nên cung vô hạn không bao giờ bão hòa; dfs lấy min với sức chứa thật nên không tràn.

Bước 3: đáp án sum - flow: lấy tất cả lợi rồi trừ phần phải bỏ. Không chọn cạnh nào cho lát cắt bằng $\sum w$ , nên đáp án không bao giờ âm.

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using 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';
}

Input2 1
3 4
1 2 10

Output3

Dinic trên $n + m + 2$ đỉnh, $3m + n$ cung.

Khi đi thi

Thấy “tách $s$ khỏi $t$ ít nhất”, “ghép nhiều nhất”, “nhiều đường không chung cạnh nhất”, “chọn tập có ràng buộc kéo theo”: dựng mạng rồi luồng cực đại. Phần khó là dựng đúng mạng; vẽ nó ra trên ví dụ nhỏ.
Giới hạn trên đỉnh thì tách mỗi đỉnh thành hai nút vào ra nối bằng cung sức chứa bằng giới hạn; cạnh vô hướng là cặp cung cùng sức chứa hai chiều.
Dinic với danh sách cạnh đánh số cặp $e, e \oplus 1$ đủ nhanh cho mạng cỡ $10^4$ đỉnh và $10^5$ cạnh trong đa số bài; vô hạn đặt bằng $4 \cdot 10^{18}$ và không cộng vào.

Tóm tắt

Đồ thị dư gồm cung xuôi $c - f$ và cung ngược $f$ ; luồng cực đại khi không còn đường tăng luồng.
Dinic: BFS phân mức, DFS đẩy luồng chặn với con trỏ cung, lặp tới khi $t$ không tới được.
Luồng cực đại bằng lát cắt nhỏ nhất; phía nguồn là các đỉnh tới được trong đồ thị dư cuối.
Ghép cặp hai phía: nguồn → $A$ → $B$ → đích, sức chứa 1; cặp là cung bão hòa.
Chọn dự án: lợi nối từ nguồn, chi phí nối tới đích, kéo theo là cung vô hạn; đáp án tổng lợi trừ lát cắt.

Bài tập

Trạm Trung Chuyểncanuc80k4900Luồng cực đại trực tiếp trên mạng có hướng với nguồn 1 và đích

n

LQDOJ

Mạng Cáp Hai Chiềucanuc80k4902Mạng vô hướng, mỗi cạnh là cặp cung cùng sức chứa hai chiều;

n

tới 5000 nên Dinic với con trỏ cung.

LQDOJ

Biên Bản Dòng Chảycanuc80k4903Chạy luồng rồi in luồng trên từng cung gốc có luồng dương, bằng sức chứa ban đầu trừ sức chứa còn lại.

LQDOJ

Vành Đai Phòng Thủcanuc80k4904Lát cắt nhỏ nhất giữa hai trạm cho trước trên mạng có hướng.

LQDOJ

Bảng Đánh Dấucanuc80k4907Hàng nối nguồn với sức chứa số ô cần đánh dấu của hàng, cột nối đích theo số của cột, ô là cung hàng → cột sức chứa 1; có lời giải khi luồng bằng tổng.

LQDOJ

Phân Bổ Sau Một Chặngcanuc80k4908Mạng hai lớp: nguồn → thành phố

i

sức chứa

a_i

, thành phố

i

→ bản sao

j

khi

i = j

hoặc kề nhau, bản sao

j

→ đích sức chứa

b_j

; đủ khi luồng bằng cả hai tổng.

LQDOJ

Các Tuyến Không Trùng Cạnhcanuc80k4909Số đường không chung cạnh là luồng với sức chứa 1; in đường bằng cách đi theo các cung có luồng từ 1, đánh dấu đã dùng.

LQDOJ

Phía Nguồn Của Lát Cắtcanuc80k4911Sau luồng cực đại, in các đỉnh tới được từ nguồn trong đồ thị dư.

LQDOJ

Kho Quà Theo Nhómcanuc80k4912Nguồn → trẻ em (1) → đồ chơi (1) → nhóm (giới hạn nhóm) → đích; đồ chơi không thuộc nhóm nào nối thẳng tới đích.

LQDOJ

Kết Quả Không Trùngcanuc80k4913Ghép mỗi cặp số với một kết quả khác nhau trong ba phép tính: ghép cặp hai phía giữa cặp và các giá trị kết quả đã nén.

LQDOJ

Dọn Sạch Lưới Xucanuc80k4914Mỗi đồng xu nối hàng với cột; số lần ít nhất là phủ đỉnh nhỏ nhất của đồ thị hai phía, bằng ghép cực đại (định lý König), in phủ từ lát cắt.

LQDOJ

Lát Domino Tối Đacanuc80k4915Tô ô theo tính chẵn lẻ của

i + j

, ghép ô đen với ô trắng kề; domino là cặp ghép, in theo hướng của cặp.

LQDOJ

Quân Cờ Trong Khungcanuc80k4916Nguồn → hàng → quân cờ (tách thành hai nút sức chứa 1) → cột → đích; mỗi quân cờ nối các hàng và cột trong khung của nó.

LQDOJ

Bàn Tròn Tổng Nguyên Tốcanuc80k4924Tổng hai số nguyên tố lớn hơn 2 thì một chẵn một lẻ: số chẵn và lẻ ở hai phía, mỗi đỉnh có đúng hai hàng xóm (sức chứa 2), rồi tách thành các vòng.

LQDOJ

Đặt Chốt Trên Mạngcanuc80k4932Lát cắt đỉnh nhỏ nhất: tách mỗi đỉnh thành vào và ra với sức chứa bằng chi phí, cạnh là cung vô hạn hai chiều; in các đỉnh có cung vào ra bị cắt.

LQDOJ

Đọc thêm

Bài toán Luồng cực đại trên mạngVNOI WikiĐồ thị dư, Ford-Fulkerson, Dinic, viết bằng tiếng Việt.
Ứng dụng của luồng trên mạngVNOI WikiCác dạng dựng mạng hay gặp.
Maximum flow - Dinic's algorithmcp-algorithmsChứng minh và cài đặt Dinic.
Maximum FlowUSACO GuideLuồng cực đại, lát cắt nhỏ nhất và bài luyện.