Flow Modeling

IGhép cặp hai phía và phủ đỉnh

Một câu lạc bộ có bốn bạn ở nhóm A và ba bạn ở nhóm B, cùng bảy cặp có thể biểu diễn chung: $(1, 1)$, $(1, 2)$, $(2, 1)$, $(2, 3)$, $(3, 2)$, $(4, 2)$, $(4, 3)$, số đầu là bạn nhóm A, số sau là bạn nhóm B. Mỗi bạn chỉ vào nhiều nhất một cặp; chọn được nhiều cặp nhất là bao nhiêu? Ba cặp $(1, 1)$, $(2, 3)$, $(3, 2)$ không chung người nào, và không thể chọn bốn cặp vì nhóm B chỉ có ba bạn.

Đồ thị mà các đỉnh chia thành hai nhóm, mỗi cạnh nối một đỉnh nhóm này với một đỉnh nhóm kia, gọi là đồ thị hai phía (bipartite graph). Một tập cạnh không có hai cạnh nào chung đỉnh gọi là một cặp ghép (matching); bài toán trên là tìm cặp ghép lớn nhất, tức có nhiều cạnh nhất.

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

Trên mạng mà mọi sức chứa bằng $1$, Dinic chạy nhanh hơn hẳn cận chung $O(V^2 E)$: chỉ cần $O(\sqrt V)$ pha, nên cả thuật toán tốn $O(E\sqrt V)$ (xem ô Chứng minh). Với các bài ghép cặp thường gặp khi thi, khuôn Dinic là đủ nhanh.

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

Đề. Có $n \le 500$ bạn ở nhóm A, $m \le 500$ bạn ở nhóm B, và $k \le 1000$ cặp có thể biểu diễn chung, mỗi cặp gồm một bạn mỗi nhóm. Chọn nhiều cặp nhất, mỗi bạn 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. Nguồn là đỉnh $0$, nhóm A là các đỉnh $1$ tới $n$, nhóm B 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 id giữ số hiệu cung của từng cặp. Chạy Dinic xong, cung của một cặp hết sức chứa nghĩa là đang chở $1$, tức 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ì bạn ở nhóm A 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;
ll n, m, k, cap[M];
int ec, to[M], lv[N], it[N], ea[M], eb[M], id[M];
vector<int> g[N];

int addEdge(int u, int 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;
}

bool bfs(int s, int t) {
    memset(lv, -1, sizeof(lv));
    queue<int> q;
    q.push(s);
    lv[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int 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(int u, int t, ll f) {
    if (u == t) return f;
    for (; it[u] < (int)g[u].size(); it[u]++) {
        int 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 maxFlow(int s, int t) {
    ll flow = 0, f;
    while (bfs(s, t)) {
        memset(it, 0, sizeof(it));
        while ((f = dfs(s, t, 1e18)) > 0) flow += f;
    }
    return flow;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    int s = 0, t = n + m + 1;
    for (int i = 1; i <= n; i++) addEdge(s, i, 1);
    for (int j = 1; j <= m; j++) addEdge(n + j, t, 1);
    for (int i = 1; i <= k; i++) {
        cin >> ea[i] >> eb[i];
        id[i] = addEdge(ea[i], n + eb[i], 1);
    }
    cout << maxFlow(s, t) << '\n';
    for (int i = 1; i <= k; i++)
        if (cap[id[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 xuôi, cần cỡ $6 \cdot 10^4$ bước.

Cặp ghép lớn nhất còn trả lời một câu hỏi tưởng như ngược lại. Cho một lưới có vài đồng xu, mỗi thao tác lấy hết xu trên một hàng hay một cột; cần ít nhất bao nhiêu thao tác? Coi mỗi hàng là một đỉnh nhóm A, mỗi cột là một đỉnh nhóm B, mỗi đồng xu ở ô $(r, c)$ là một cạnh nối hàng $r$ với cột $c$. Chọn một tập hàng và cột lấy hết xu nghĩa là mọi cạnh có ít nhất một đầu được chọn. Một tập đỉnh như vậy gọi là một phủ đỉnh (vertex cover).

Lý luận ở cuối câu hỏi đúng với mọi đồ thị: phủ đỉnh nào cũng có ít nhất số đỉnh bằng một cặp ghép bất kỳ, vì các cạnh của cặp ghép không chung đỉnh. Trên đồ thị hai phía, hai số này còn bằng nhau, và đây là định lý König: phủ đỉnh nhỏ nhất có đúng bằng số cạnh của cặp ghép lớn nhất. Cách tìm phủ đỉnh cũng đến từ lát cắt: dựng mạng ghép cặp nhưng cho các cung từ A sang B sức chứa vô hạn, chạy luồng cực đại, rồi gọi $S$ là các đỉnh tới được từ $s$ trên đồ thị dư. Phủ đỉnh gồm các đỉnh nhóm A không thuộc $S$ và các đỉnh nhóm B thuộc $S$.

Ví dụDọn Sạch Lưới Xu

Đề. Lưới $n \times n$ ($n \le 100$), mỗi ô rỗng . hoặc có một đồng xu o. Mỗi thao tác chọn một hàng hay một cột và lấy hết xu trên đó. Tìm số thao tác ít nhất và in các thao tác: 1 x là chọn hàng $x$, 2 x là chọn cột $x$.

Lời giải. Hàng là nhóm A (đỉnh $1$ tới $n$), cột là nhóm B (đỉnh $n + 1$ tới $2n$), mỗi đồng xu ở ô $(r, c)$ là cung từ hàng $r$ tới cột $c$ với sức chứa vô hạn. Theo định lý König, số thao tác ít nhất bằng luồng cực đại. Chạy Dinic xong, gọi bfs thêm một lần: hàng có lv âm (không thuộc $S$) và cột có lv không âm (thuộc $S$) là các thao tác cần làm. Lưới có tới $10^4$ đồng xu, nên mạng có $2n + 2$ đỉnh và tới $10^4 + 2n$ cung xuôi.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 205, M = 2.1e4;
ll n, cap[M];
int ec, to[M], lv[N], it[N];
string a[N];
vector<int> g[N];

void addEdge(int u, int 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(int s, int t) {
    memset(lv, -1, sizeof(lv));
    queue<int> q;
    q.push(s);
    lv[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int 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(int u, int t, ll f) {
    if (u == t) return f;
    for (; it[u] < (int)g[u].size(); it[u]++) {
        int 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 maxFlow(int s, int t) {
    ll flow = 0, f;
    while (bfs(s, t)) {
        memset(it, 0, sizeof(it));
        while ((f = dfs(s, t, 1e18)) > 0) flow += f;
    }
    return flow;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int s = 0, t = 2 * n + 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = " " + a[i];
        addEdge(s, i, 1);
        addEdge(n + i, t, 1);
    }
    for (int r = 1; r <= n; r++)
        for (int c = 1; c <= n; c++)
            if (a[r][c] == 'o') addEdge(r, n + c, 1e18);
    cout << maxFlow(s, t) << '\n';
    bfs(s, t);
    for (int r = 1; r <= n; r++)
        if (lv[r] < 0) cout << 1 << ' ' << r << '\n';
    for (int c = 1; c <= n; c++)
        if (lv[n + c] >= 0) cout << 2 << ' ' << c << '\n';
}

ChạyInput3
..o
o.o
...

Output2
1 1
1 2

Độ phức tạp: $O(E\sqrt V)$ với $V = 2n + 2 \le 202$ và $E \le 10^4 + 200$ cung xuôi; cả chương trình chỉ cỡ $10^5$ bước.

IITách đỉnh và đường đi rời nhau

Mạng ở hình dưới có $7$ nút và $9$ liên kết một chiều. Ta muốn đi từ nút $1$ tới nút $7$ nhiều lần nhất, mỗi liên kết dùng không quá một lần trong tất cả các lần đi. Ba đường $1 \to 2 \to 7$, $1 \to 3 \to 5 \to 7$ và $1 \to 4 \to 6 \to 7$ không chung liên kết nào, và không có đường thứ tư vì nút $1$ chỉ có ba liên kết đi ra.

Cho mỗi liên kết sức chứa $1$, mỗi đường đi là một đơn vị luồng, nên số đường không chung cạnh nhiều nhất bằng luồng cực đại. Ngược lại, từ một luồng nguyên giá trị $k$ ta luôn tách được $k$ đường như vậy: đi từ nguồn theo các cung đang chở luồng chưa dùng tới, đánh dấu cung đã đi, cho tới khi gặp đích. Đường đi không bao giờ kẹt giữa chừng: ở mỗi đỉnh trung gian, số cung chở luồng đi vào bằng số cung chở luồng đi ra, nên đã vào được thì luôn còn một cung chưa dùng để đi ra.

Ví dụCác Tuyến Không Trùng Cạnh

Đề. Có $n \le 500$ nút và $m \le 1000$ liên kết có hướng, không có hai liên kết trùng nhau. Tìm số đường nhiều nhất từ nút $1$ tới nút $n$ sao cho không liên kết nào được dùng ở hai đường, và in các đường.

Lời giải. Mỗi liên kết là một cung sức chứa $1$; luồng cực đại $k$ là số đường. Để in, ta đi $k$ lần từ nút $1$. Mỗi bước ở nút $u$, tìm một cung xuôi của $u$ đang chở luồng mà chưa dùng: cung xuôi có số hiệu chẵn, và nó chở luồng khi sức chứa dư bằng $0$. Đánh dấu cung đó, đi sang đầu kia, và dừng khi tới nút $n$. Theo lý luận ở trên, mỗi lần đi đều tới được $n$.

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

void addEdge(int u, int 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(int s, int t) {
    memset(lv, -1, sizeof(lv));
    queue<int> q;
    q.push(s);
    lv[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int 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(int u, int t, ll f) {
    if (u == t) return f;
    for (; it[u] < (int)g[u].size(); it[u]++) {
        int 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 maxFlow(int s, int t) {
    ll flow = 0, f;
    while (bfs(s, t)) {
        memset(it, 0, sizeof(it));
        while ((f = dfs(s, t, 1e18)) > 0) flow += f;
    }
    return flow;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b, 1);
    }
    ll k = maxFlow(1, n);
    cout << k << '\n';
    for (int p = 1; p <= k; p++) {
        int u = 1, len = 0;
        path[++len] = 1;
        while (u != n) {
            for (int e : g[u])
                if (e % 2 == 0 && cap[e] == 0 && !used[e]) {
                    used[e] = true;
                    u = to[e];
                    break;
                }
            path[++len] = u;
        }
        cout << len << '\n';
        for (int i = 1; i <= len; i++) cout << path[i] << (i == len ? '\n' : ' ');
    }
}

ChạyInput7 9
1 2
1 3
1 4
2 7
3 5
5 7
4 6
6 7
3 6

Output3
3
1 2 7
4
1 3 5 7
4
1 4 6 7

Độ phức tạp: Dinic trên mạng sức chứa $1$ tốn $O(m\sqrt m)$; in các đường tốn $O(k(n + m))$ vì mỗi bước duyệt danh sách cung của một nút; với $n = 500$, $m = 1000$ chương trình chạy tức thì.

Khi giới hạn đặt trên đỉnh thay vì trên cạnh, chẳng hạn mỗi nút chỉ được đi qua một lần, hay mỗi nút chỉ xử lý được $c(v)$ đơn vị, ta tách đỉnh: thay đỉnh $v$ bằng hai đỉnh $v_1$ và $v_2$ nối bằng cung $v_1 \to v_2$ sức chứa $c(v)$; mọi cung đi vào $v$ đổi thành đi vào $v_1$, mọi cung đi ra khỏi $v$ đổi thành đi ra từ $v_2$. Đơn vị luồng nào đi qua $v$ cũng phải qua cung $v_1 \to v_2$, nên tổng luồng qua $v$ không vượt $c(v)$.

Với $c(v) = 1$ cho mọi đỉnh trung gian, luồng cực đại là số đường nhiều nhất từ $s$ tới $t$ không chung đỉnh trung gian nào. Bài ngược lại cũng giải được: xóa các đỉnh có tổng chi phí nhỏ nhất để tách $s$ khỏi $t$ là lát cắt nhỏ nhất trên mạng đã tách đỉnh, trong đó cung $v_1 \to v_2$ mang chi phí của $v$ và mọi cung khác có sức chứa vô hạn, để lát cắt chỉ được cắt ở các đỉnh.

Sử dụng kiến thức này cũng có thể giải bài phủ đồ thị có hướng không chu trình bằng ít đường đi nhất, mỗi đỉnh thuộc đúng một đường: tách mỗi đỉnh thành một bản “ra” bên trái và một bản “vào” bên phải, mỗi cung $u \to v$ thành cạnh từ bản ra của $u$ tới bản vào của $v$. Mỗi cạnh của một cặp ghép nối hai đỉnh liên tiếp trên cùng một đường, mỗi lần nối giảm số đường đi một, nên số đường ít nhất bằng $n$ trừ cặp ghép lớn nhất.

IIIChọn dự án bằng lát cắt nhỏ nhất

Một công ty có hai dự án: dự án D1 lãi $6$ và cần công cụ C1; dự án D2 lãi $2$ và cần cả hai công cụ C1, C2. Mua C1 tốn $4$, mua C2 tốn $3$. Làm dự án nào thì phải mua đủ công cụ nó cần; một công cụ đã mua dùng chung được cho nhiều dự án. Thử hết các cách: không làm gì được $0$; chỉ làm D1 được $6 - 4 = 2$; chỉ làm D2 được $2 - 4 - 3 = -5$; làm cả hai được $8 - 7 = 1$. Cách tốt nhất là chỉ làm D1, lãi $2$.

Tổng quát, có một số dự án, mỗi dự án có một khoản lãi, và một số công cụ, mỗi công cụ có một chi phí; mỗi dự án cần một số công cụ. Chọn các dự án và công cụ sao cho tổng lãi trừ tổng chi phí lớn nhất. Đây là bài toán chọn dự án (project selection), còn gọi là bài toán bao đóng có trọng số lớn nhất. Ta dựng mạng:

• nguồn $s$ nối tới mỗi dự án bằng cung có sức chứa bằng lãi 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ụ;
• dự án $x$ cần công cụ $y$ thì thêm cung $x \to y$ sức chứa vô hạn, trong code là $10^{18}$.

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 của mọi dự án trừ đi sức chứa của lát cắt nhỏ nhất. Ở ví dụ trên, tổng lãi là $8$, lát cắt nhỏ nhất có $S = \{s, D1, C1\}$ và sức chứa $6$, nên lãi lớn nhất là $2$, đúng như khi thử hết.

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 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 $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 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 $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 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 = 1e4 + 5;
ll n, m, cap[M];
int ec, to[M], lv[N], it[N];
vector<int> g[N];

void addEdge(int u, int 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(int s, int t) {
    memset(lv, -1, sizeof(lv));
    queue<int> q;
    q.push(s);
    lv[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int 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(int u, int t, ll f) {
    if (u == t) return f;
    for (; it[u] < (int)g[u].size(); it[u]++) {
        int 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 maxFlow(int s, int t) {
    ll flow = 0, f;
    while (bfs(s, t)) {
        memset(it, 0, sizeof(it));
        while ((f = dfs(s, t, 1e18)) > 0) flow += f;
    }
    return flow;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int s = 0, t = n + m + 1;
    for (int i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        addEdge(m + i, t, a);
    }
    ll sum = 0;
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        sum += w;
        addEdge(s, i, w);
        addEdge(i, m + u, 1e18);
        addEdge(i, m + v, 1e18);
    }
    cout << sum - maxFlow(s, t) << '\n';
}

ChạyInput2 1
3 4
1 2 10

Output3

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

IVMở rộng: luồng có cận dưới

Có khi đề bắt mỗi cung $u \to v$ chở ít nhất $l(u, v)$ và nhiều nhất $c(u, v)$, chẳng hạn mỗi tuyến đường phải có tối thiểu một số chuyến. Câu hỏi đầu tiên là có luồng nào thỏa mọi cận dưới không, gọi là luồng khả thi. Ta xét trước trường hợp không có nguồn, đích: mọi đỉnh đều phải cân bằng vào ra.

Ý tưởng là cho mỗi cung chở sẵn phần bắt buộc $l(u, v)$, rồi tìm phần còn lại. Chở sẵn $l$ trên cung $u \to v$ làm $v$ thừa $l$ đơn vị và $u$ thiếu $l$ đơn vị; phần còn lại của cung chỉ được chở thêm tối đa $c - l$. Gọi $ex(v)$ là tổng phần bắt buộc đi vào $v$ trừ tổng phần bắt buộc đi ra khỏi $v$. Đỉnh có $ex(v) > 0$ đang thừa và phải đẩy phần thừa đi, đỉnh có $ex(v) < 0$ đang thiếu và phải nhận thêm. Ta thêm một nguồn phụ $S'$ nối tới mỗi đỉnh thừa bằng cung sức chứa $ex(v)$, và mỗi đỉnh thiếu nối tới đích phụ $T'$ bằng cung sức chứa $-ex(v)$. Có luồng khả thi khi và chỉ khi luồng cực đại từ $S'$ tới $T'$ làm đầy mọi cung ra khỏi $S'$; khi đó luồng trên cung $u \to v$ là $l(u, v)$ cộng phần chạy trên cung sức chứa $c - l$.

for (int i = 1; i <= m; i++) {
    addEdge(eu[i], ev[i], hi[i] - lo[i]);
    ex[ev[i]] += lo[i];
    ex[eu[i]] -= lo[i];
}
ll need = 0;
for (int v = 1; v <= n; v++) {
    if (ex[v] > 0) addEdge(S, v, ex[v]), need += ex[v];
    if (ex[v] < 0) addEdge(v, T, -ex[v]);
}
bool feasible = maxFlow(S, T) == need;

Độ phức tạp: một lần chạy Dinic trên mạng thêm hai đỉnh và không quá $n$ cung; cùng cỡ với một bài luồng cực đại thường.

Khi mạng có nguồn $s$ và đích $t$ thật, chỉ $s$ và $t$ được lệch vào ra. Ta thêm cung $t \to s$ sức chứa vô hạn để luồng chạy vòng về, biến bài toán thành bài không nguồn, đích ở trên. Nếu có luồng khả thi, luồng trên cung $t \to s$ là giá trị của một luồng khả thi từ $s$ tới $t$. Muốn luồng lớn nhất, ta xóa cung $t \to s$ (đặt sức chứa của nó và cung ngược bằng $0$) rồi chạy tiếp luồng cực đại từ $s$ tới $t$ trên đồ thị dư, cộng thêm vào giá trị khả thi; muốn luồng nhỏ nhất thì chạy luồng cực đại từ $t$ về $s$ và trừ đi.