Network Flow

Đồ thị dư và 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.

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. Trong dfs, con trỏ it[u] nhớ cung đang thử của u: cung đã thử mà không đẩy được (bão hòa hoặc dẫn vào ngõ cụt) thì cả pha này không thử lại.

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

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.

Các pha. addEdge, bfs, dfs như trên. 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.

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

#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

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

Thiếu con trỏ it[u] thì chương trình vẫn đúng, chỉ chậm: mỗi lần dfs lại đi qua mọi cung đã hỏng từ đầu.

Chỉ một mảng it mà nhanh gấp hơn 10 lần, và chênh lệch càng lớn khi đồ thị càng dày.

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.

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.

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.

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

#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], 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';
}

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

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.

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

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

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

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

ChạyInput5 2 4
3 4
0 1
1 3
0 2
2 4

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ả.

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

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.

for (ll i = 1; i <= k; i++)
    if (cap[eid[i]] == 0) cout << ea[i] << ' ' << eb[i] << '\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

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

Chọn dự án

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.

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”.

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.

#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

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