Bài 43: Ghép cặp trên đồ thị hai phía và luồng cực đại trong C++ và Python: thuật toán Kuhn, Edmonds–Karp, lát cắt nhỏ nhất, định lý König
Lời mở đầu
Một đề thi quen thuộc: có $n$ bạn và $k$ công việc, mỗi bạn chỉ làm được vài việc, mỗi việc chỉ cần một bạn. Hỏi giao được nhiều nhất bao nhiêu việc? Thử tham lam “ai chọn trước thì lấy trước” rất dễ sai: một bạn chọn mất việc duy nhất mà bạn khác làm được. Quay lui thì bùng nổ. Cách đúng là một thuật toán ngắn chưa tới 15 dòng: ghép cặp bằng đường tăng (thuật toán Kuhn). Mở rộng ý tưởng đó lên đồ thị có trọng số, ta được luồng cực đại: bài toán “bơm được bao nhiêu nước từ nguồn tới bể chứa qua một mạng ống có giới hạn”.
Bài này dùng rất nhiều BFS và DFS từ bài 21, cách nghĩ “đi trên đồ thị phụ” giống bài 29 Đường đi ngắn nhất, và ở phần lát cắt em sẽ gặp lại câu hỏi “cắt cạnh nào thì đồ thị rời ra” của bài 36 về cầu và khớp, nhưng lần này là cắt nhiều cạnh với chi phí nhỏ nhất. Luồng cực đại là kiến thức nền của đội tuyển quốc gia, còn ghép cặp thì gặp cả ở đề HSG tỉnh.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Đồ thị hai phía và kiểm tra bằng tô 2 màu
Đồ thị vô hướng gọi là hai phía (bipartite) nếu chia được tập đỉnh thành hai nhóm $L$ và $R$ sao cho mọi cạnh đều nối một đỉnh của $L$ với một đỉnh của $R$, không có cạnh nào nằm gọn trong một nhóm. Rất nhiều bài toán thực tế tự nhiên có dạng này: người và việc, học sinh và câu lạc bộ, hàng và cột của bảng, ô đen và ô trắng của bàn cờ.
Nói cách khác: đồ thị hai phía là đồ thị tô được bằng 2 màu sao cho hai đầu mỗi cạnh khác màu. Cách kiểm tra rất tự nhiên: BFS từ một đỉnh, tô nó màu 1; mỗi đỉnh mới gặp được tô ngược màu với đỉnh vừa đi tới nó. Nếu lúc nào đó gặp một cạnh mà hai đầu đã cùng màu thì không thể tô, đồ thị không hai phía. Đồ thị nhiều thành phần liên thông thì BFS lần lượt từng thành phần, mỗi thành phần tô độc lập.
Hình 1. Bên trái: đồ thị 6 đỉnh tô được 2 màu, nhóm xanh {1, 3, 5} và nhóm vàng {2, 4, 6}. Bên phải: tam giác (chu trình 3 đỉnh), đỉnh 3 kề cả hai màu nên không tô được.
| Bước | Lấy ra | Các đỉnh kề | Hành động | Màu 1..6 |
|---|---|---|---|---|
| 0 | – | – | tô đỉnh 1 màu 1 | 1 · · · · · |
| 1 | 1 | 2, 4 | tô 2 và 4 màu 2 | 1 2 · 2 · · |
| 2 | 2 | 1, 3 | 1 khác màu (tốt), tô 3 màu 1 | 1 2 1 2 · · |
| 3 | 4 | 3, 1, 5 | 3, 1 khác màu, tô 5 màu 1 | 1 2 1 2 1 · |
| 4 | 3 | 2, 4 | đều khác màu | 1 2 1 2 1 · |
| 5 | 5 | 4, 6 | tô 6 màu 2 | 1 2 1 2 1 2 |
Bảng 1. BFS tô màu đồ thị bên trái Hình 1 (cạnh nhập theo thứ tự 1–2, 2–3, 3–4, 4–1, 4–5, 5–6). Không có xung đột nên đồ thị hai phía.
Xem code C++ / Python: kiểm tra đồ thị hai phía bằng bfs tô 2 màu (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> color(n + 1, 0); // 0: chưa tô, 1 và 2: hai màu
for(int s = 1; s <= n; s++){
if(color[s]) continue; // mỗi thành phần liên thông BFS một lần
color[s] = 1;
queue<int> q; q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
for(int v : adj[u]){
if(color[v] == 0){
color[v] = 3 - color[u]; // tô màu ngược với u
q.push(v);
} else if(color[v] == color[u]){ // hai đầu một cạnh cùng màu
cout << "NO";
return 0;
}
}
}
}
cout << "YES\n";
for(int u = 1; u <= n; u++) cout << color[u] << " ";
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v); adj[v].append(u)
color = [0] * (n + 1) # 0: chưa tô, 1 và 2: hai màu
for s in range(1, n + 1):
if color[s]:
continue
color[s] = 1
q = deque([s])
while q:
u = q.popleft()
for v in adj[u]:
if color[v] == 0:
color[v] = 3 - color[u] # tô màu ngược với u
q.append(v)
elif color[v] == color[u]: # hai đầu một cạnh cùng màu
print("NO")
return
print("YES")
print(*color[1:])
main()for ngoài cùng duyệt mọi đỉnh chưa tô.2. Có cạnh khuyên $u$–$u$ thì đồ thị chắc chắn không hai phía (chu trình độ dài 1). Code trên xử lý đúng vì khi xét $v = u$ thì
color[v] == color[u].Phần 2Ghép cặp cực đại bằng đường tăng (thuật toán Kuhn)
Cho đồ thị hai phía với phía trái $L$, phía phải $R$. Một cặp ghép (matching) là một tập cạnh không có hai cạnh nào chung đỉnh: mỗi người nhận tối đa một việc, mỗi việc giao cho tối đa một người. Bài toán: tìm cặp ghép có nhiều cạnh nhất. Đỉnh thuộc một cạnh của cặp ghép gọi là đã ghép, ngược lại là tự do.
Đường tăng (augmenting path) là một đường đi bắt đầu ở một đỉnh trái tự do, kết thúc ở một đỉnh phải tự do, và các cạnh xen kẽ: chưa ghép, đã ghép, chưa ghép, …, chưa ghép. Đường như vậy luôn có số cạnh chưa ghép nhiều hơn số cạnh đã ghép đúng 1. Nếu ta lật nó (cạnh chưa ghép thành ghép, cạnh đã ghép bỏ ra) thì vẫn được một cặp ghép hợp lệ, và nhiều hơn đúng 1 cạnh.
Hình 2. Cặp ghép gồm L1–R2, L2–R1, L3–R3 (xanh lá). L4 tự do, R4 tự do. Đường tăng L4 → R3 → L3 → R4: nét đứt là cạnh chưa ghép, nét liền cam là cạnh đang ghép. Lật đường này được 4 cặp: L3 “nhường” R3 cho L4 và chuyển sang R4.
Thuật toán Kuhn lần lượt xét từng đỉnh trái $u$ và tìm một đường tăng xuất phát từ $u$ bằng DFS. Hàm tryKuhn(u) thử từng đỉnh phải $v$ kề với $u$:
- nếu $v$ tự do: ghép $u$ với $v$, xong;
- nếu $v$ đang ghép với $w$: gọi đệ quy
tryKuhn(w), tức là “nhờ” $w$ tìm chỗ khác. Nếu $w$ tìm được thì $v$ được nhường lại cho $u$.
Mảng vis đánh dấu các đỉnh phải đã thử trong lượt hiện tại, để DFS không đi vòng mãi. Chuỗi lời gọi đệ quy thành công chính là một đường tăng, và các lệnh gán matchR[v] = u khi đệ quy trả về chính là thao tác lật đường đó. Mô phỏng dưới đây chạy trên đúng đồ thị Hình 2: ở lượt L3 có một nhánh thất bại (L1 nhờ L2, L2 không có chỗ nào khác), còn lượt L4 thì phải đi qua 2 lần “nhờ”:
| Lượt | Diễn biến DFS | Kết quả | Cặp ghép sau lượt |
|---|---|---|---|
| L1 | R1 tự do | ghép L1–R1 | L1–R1 |
| L2 | R1 của L1 → nhờ L1: R1 đã thăm, R2 tự do | đường L2–R1–L1–R2 | L1–R2, L2–R1 |
| L3 | R2 của L1 → nhờ L1: R1 của L2 → nhờ L2: hết cách ✗; R3 tự do | ghép L3–R3 | L1–R2, L2–R1, L3–R3 |
| L4 | R3 của L3 → nhờ L3: R2 của L1 → nhờ L1 ✗ (như trên); R3 đã thăm; R4 tự do | đường L4–R3–L3–R4 | L1–R2, L2–R1, L3–R4, L4–R3 |
Bảng 2. Bốn lượt của thuật toán Kuhn trên đồ thị Hình 2. Kết quả: 4 cặp, tức là ghép được hết.
Vì sao đúng? Định lý Berge: một cặp ghép $M$ là lớn nhất khi và chỉ khi không còn đường tăng. Chiều “có đường tăng thì chưa lớn nhất” thì rõ (lật là tăng 1). Chiều ngược lại: giả sử có cặp ghép $M^*$ lớn hơn $M$. Xét các cạnh thuộc đúng một trong hai tập $M$, $M^*$: mỗi đỉnh chạm tối đa 2 cạnh như vậy (một của $M$, một của $M^*$), nên chúng tạo thành các đường và chu trình mà cạnh $M$, $M^*$ xen kẽ. Chu trình xen kẽ có số cạnh hai loại bằng nhau. Vì $|M^*| > |M|$ nên phải có một đường chứa nhiều cạnh $M^*$ hơn, và đường đó chính là một đường tăng của $M$. Mâu thuẫn.
Còn một chi tiết: Kuhn chỉ thử mỗi đỉnh trái một lần. Nếu lượt của $u$ thất bại, có thể sau này $u$ lại có đường tăng không? Không: người ta chứng minh được nếu không có đường tăng từ $u$ thì sau khi lật các đường tăng khác vẫn không có. Vì vậy chạy $|L|$ lượt là đủ. Mỗi lượt là một DFS $O(V + E)$, tổng $O(V \cdot E)$, thoải mái với $V \le 1000$, $E \le 10^4$.
Xem code C++ / Python: ghép cặp cực đại bằng thuật toán kuhn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int nL, nR, m;
vector<int> adj[100005];
int matchR[100005], matchL[100005]; // 0: chưa ghép
int vis[100005], stamp = 0; // vis[v] == stamp: đã thăm trong lượt này
bool tryKuhn(int u){
for(int v : adj[u]){
if(vis[v] == stamp) continue;
vis[v] = stamp;
if(matchR[v] == 0 || tryKuhn(matchR[v])){ // v trống, hoặc người giữ v đổi được
matchR[v] = u;
return true;
}
}
return false;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> nL >> nR >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
int res = 0;
for(int u = 1; u <= nL; u++){
stamp++; // "xoá" vis trong O(1)
if(tryKuhn(u)) res++;
}
for(int v = 1; v <= nR; v++) if(matchR[v]) matchL[matchR[v]] = v;
cout << res << "\n";
for(int u = 1; u <= nL; u++) if(matchL[u]) cout << u << " " << matchL[u] << "\n";
return 0;
}import sys
sys.setrecursionlimit(20000)
def main():
data = sys.stdin.buffer.read().split()
nL, nR, m = int(data[0]), int(data[1]), int(data[2])
adj = [[] for _ in range(nL + 1)]
for i in range(m):
adj[int(data[3 + 2 * i])].append(int(data[4 + 2 * i]))
match_r = [0] * (nR + 1) # 0: chưa ghép
vis = [0] * (nR + 1)
def try_kuhn(u, stamp):
for v in adj[u]:
if vis[v] == stamp:
continue
vis[v] = stamp
if match_r[v] == 0 or try_kuhn(match_r[v], stamp):
match_r[v] = u
return True
return False
res = 0
for u in range(1, nL + 1):
if try_kuhn(u, u): # dùng chính u làm "dấu thời gian"
res += 1
match_l = [0] * (nL + 1)
for v in range(1, nR + 1):
if match_r[v]:
match_l[match_r[v]] = v
out = [str(res)] + ['%d %d' % (u, match_l[u]) for u in range(1, nL + 1) if match_l[u]]
print('\n'.join(out))
main()memset(vis) mỗi lượt (tốn $O(|R|)$), dùng vis[v] == stamp và tăng stamp mỗi lượt, như trong code trên.2. Ghép tham lam trước: duyệt qua mỗi đỉnh trái, nếu có đỉnh phải kề còn tự do thì ghép luôn; sau đó mới chạy Kuhn cho các đỉnh còn lại. Thực tế nhanh hơn nhiều lần.
3. Python: đệ quy sâu tới $|L|$ tầng, nhớ
sys.setrecursionlimit. Nếu $|L|$ cỡ $10^4$ trở lên nên chuyển sang Hopcroft–Karp hoặc Dinic (Phần 5).Phần 3Luồng cực đại: mạng, đồ thị thặng dư và Edmonds–Karp
Mạng luồng là một đồ thị có hướng, mỗi cung $u \to v$ có dung lượng $c(u, v) \ge 0$ (sức chứa của ống nước), cùng hai đỉnh đặc biệt: đỉnh phát $s$ (nguồn) và đỉnh thu $t$ (bể chứa). Một luồng gán cho mỗi cung một số $f(u, v)$ thoả hai điều kiện:
- Giới hạn dung lượng: $0 \le f(u, v) \le c(u, v)$.
- Bảo toàn: ở mọi đỉnh khác $s$ và $t$, tổng luồng chảy vào bằng tổng luồng chảy ra (nước không tự sinh ra hay mất đi giữa đường).
Giá trị của luồng là tổng luồng chảy ra khỏi $s$ (cũng bằng tổng chảy vào $t$). Bài toán luồng cực đại: tìm luồng có giá trị lớn nhất.
Ý tưởng tự nhiên: còn đường nào từ $s$ tới $t$ mà mọi cung chưa đầy thì đẩy thêm nước theo đường đó. Nhưng tham lam như vậy có thể kẹt. Xem mạng ở Hình 3: nếu đẩy 2 đơn vị theo đường 1→2→4→7 trước, từ $s$ chỉ còn đi được 1→3→4 nhưng 4→7 đã đầy, tổng mắc kẹt ở 2. Trong khi đáp án đúng là 3: 1 đơn vị theo 1→2→4→7, 1 theo 1→3→4→7, 1 theo 1→2→5→6→7.
Hình 3. (a) Đẩy tham lam 2 đơn vị theo 1→2→4→7 (đỏ: cung đã đầy). (b) Đồ thị thặng dư tương ứng: nhờ cạnh ngược 4→2 (hồng) vẫn còn đường tăng 1→3→4→2→5→6→7 (cam).
Cách sửa: cho phép “trả lại” luồng đã đẩy. Ta xây đồ thị thặng dư: với mỗi cung $u \to v$ đang có luồng $f$ trên dung lượng $c$,
- cung thuận $u \to v$ còn $c - f$: lượng còn đẩy thêm được;
- cạnh ngược $v \to u$ có $f$: lượng có thể rút bớt lại.
Một đường tăng là đường từ $s$ tới $t$ trong đồ thị thặng dư, chỉ đi qua các cạnh có giá trị dương. Đẩy $\delta$ = giá trị nhỏ nhất trên đường (nút cổ chai) dọc theo nó: đi qua cạnh thuận thì tăng luồng, đi qua cạnh ngược thì giảm luồng của cung gốc. Ở Hình 3b, đường 1→3→4→2→5→6→7 đi qua cạnh ngược 4→2: nghĩa là 1 đơn vị nước đang chảy 2→4 được “đổi hướng”, giờ đi 2→5→6→7, còn chỗ trống trên 4→7 nhường cho nước từ 3. Tổng tăng thành 3.
Edmonds–Karp = lặp “tìm đường tăng bằng BFS (đường ít cạnh nhất), đẩy nút cổ chai” tới khi BFS không tới được $t$. Dùng BFS thay vì DFS tuỳ ý là điều quan trọng: người ta chứng minh số lần tăng không quá $O(VE)$, nên tổng thời gian là $O(VE^2)$ bất kể dung lượng lớn cỡ nào.
to[], cap[]. Mỗi khi thêm cung $u \to v$ dung lượng $c$, thêm liền nhau hai cạnh: cạnh thuận ở chỉ số chẵn $2k$ (cap $= c$) và cạnh ngược ở chỉ số $2k + 1$ (cap $= 0$). Khi đó cạnh ngược của cạnh id luôn là id ^ 1. Mảng cap chính là đồ thị thặng dư: đẩy $f$ qua cạnh id thì cap[id] -= f; cap[id ^ 1] += f;. Luồng thật trên cung gốc thứ $k$ bằng cap[2k + 1].Em chạy tay chương trình trên đúng mạng Hình 3. Để ý lượt 2: BFS đi từ 4 ngược về 2 qua cạnh id 3 (cạnh ngược của 2→4), đúng như hình vẽ:
Khung chạy tay cho thấy từng dòng code, còn mô phỏng dưới đây vẽ cả mạng luồng lẫn đồ thị thặng dư sau mỗi bước. Mạng mặc định có 6 đỉnh, luồng cực đại 19. Em thử nhập lại mạng Hình 3 (n = 7, các cung 1 2 2, 2 4 2, 4 7 2, 1 3 1, 3 4 1, 2 5 1, 5 6 1, 6 7 1) để thấy cạnh ngược được dùng:
Xem code C++ / Python: luồng cực đại bằng edmonds–karp (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m, s, t;
vector<int> to;
vector<long long> cap;
vector<vector<int>> adj;
void addEdge(int u, int v, long long c){
adj[u].push_back(to.size()); to.push_back(v); cap.push_back(c); // id chẵn: thuận
adj[v].push_back(to.size()); to.push_back(u); cap.push_back(0); // id lẻ: ngược
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> s >> t;
adj.assign(n + 1, {});
for(int i = 0; i < m; i++){
int u, v; long long c;
cin >> u >> v >> c;
addEdge(u, v, c);
}
long long flow = 0;
while(true){
vector<int> par(n + 1, -1);
par[s] = -2;
queue<int> q; q.push(s);
while(!q.empty() && par[t] == -1){ // BFS trên đồ thị thặng dư
int u = q.front(); q.pop();
for(int id : adj[u])
if(par[to[id]] == -1 && cap[id] > 0){ par[to[id]] = id; q.push(to[id]); }
}
if(par[t] == -1) break; // hết đường tăng
long long f = LLONG_MAX;
for(int v = t; v != s; v = to[par[v] ^ 1]) f = min(f, cap[par[v]]);
for(int v = t; v != s; v = to[par[v] ^ 1]){ cap[par[v]] -= f; cap[par[v] ^ 1] += f; }
flow += f;
}
cout << flow;
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, m, s, t = int(data[0]), int(data[1]), int(data[2]), int(data[3])
adj = [[] for _ in range(n + 1)]
to, cap = [], []
for i in range(m):
u, v, c = int(data[4 + 3 * i]), int(data[5 + 3 * i]), int(data[6 + 3 * i])
adj[u].append(len(to)); to.append(v); cap.append(c) # id chẵn: thuận
adj[v].append(len(to)); to.append(u); cap.append(0) # id lẻ: ngược
flow = 0
while True:
par = [-1] * (n + 1)
par[s] = -2
q = deque([s])
while q and par[t] == -1: # BFS trên đồ thị thặng dư
u = q.popleft()
for e in adj[u]:
if par[to[e]] == -1 and cap[e] > 0:
par[to[e]] = e
q.append(to[e])
if par[t] == -1: # hết đường tăng
break
f, v = float('inf'), t
while v != s:
f = min(f, cap[par[v]]); v = to[par[v] ^ 1]
v = t
while v != s:
cap[par[v]] -= f; cap[par[v] ^ 1] += f; v = to[par[v] ^ 1]
flow += f
print(flow)
main()2. Tổng luồng có thể vượt
int (nhiều cung dung lượng $10^9$): dùng long long cho cap và flow.3. Cung song song (nhiều cung cùng $u \to v$) và cặp cung ngược chiều $u \to v$, $v \to u$ đều được phép, vì mỗi cung có cặp chỉ số riêng. Đừng gộp bằng ma trận kề
cap[u][v] nếu chưa hiểu rõ.Phần 4Lát cắt nhỏ nhất = luồng lớn nhất
Một lát cắt $s$–$t$ là cách chia tập đỉnh thành hai phần: $S$ chứa $s$, $T$ chứa $t$. Dung lượng lát cắt là tổng dung lượng các cung đi từ $S$ sang $T$ (cung đi từ $T$ về $S$ không tính). Xoá hết các cung đó thì không còn đường nào từ $s$ tới $t$. Bài toán lát cắt nhỏ nhất: tìm cách chia có dung lượng nhỏ nhất, chẳng hạn “phá ít đường nhất để quân địch không đi được từ $s$ tới $t$”.
Mọi luồng ≤ mọi lát cắt. Mỗi đơn vị nước đi từ $s$ (trong $S$) tới $t$ (trong $T$) phải băng qua ranh giới, chính xác hơn: giá trị luồng = (tổng luồng trên cung $S \to T$) − (tổng luồng trên cung $T \to S$) $\le$ tổng dung lượng cung $S \to T$. Vậy luồng lớn nhất không vượt quá lát cắt nhỏ nhất.
Định lý Ford–Fulkerson: hai đại lượng này bằng nhau. Khi Edmonds–Karp dừng, BFS cuối cùng trên đồ thị thặng dư không tới được $t$. Gọi $S$ là tập đỉnh tới được, $T$ là phần còn lại:
- mọi cung $u \to v$ với $u \in S$, $v \in T$ phải đầy ($f = c$), nếu không BFS đã đi qua được;
- mọi cung $v \to u$ từ $T$ về $S$ phải có luồng 0, nếu không cạnh ngược $u \to v$ còn dương và BFS đã đi qua được.
Thay vào đẳng thức ở trên: luồng = tổng dung lượng cung $S \to T$ − 0. Một luồng bằng một lát cắt thì cả hai đều tối ưu. Đồng thời đây cũng là cách truy ra lát cắt: chạy luồng cực đại, BFS thêm một lần, các cung từ đỉnh tới được sang đỉnh không tới được là lát cắt nhỏ nhất.
Mô phỏng dưới đây chạy xong luồng cực đại rồi làm đúng hai việc đó: BFS tìm phía $S$, sau đó cộng dung lượng từng cung cắt. Mạng mặc định là ví dụ kinh điển trong sách CLRS:
| Cung | Hướng | Luồng / dung lượng | Tính vào lát cắt? |
|---|---|---|---|
| 2→4 | $S \to T$ | 12 / 12 (đầy) | +12 |
| 5→4 | $S \to T$ | 7 / 7 (đầy) | +7 |
| 5→6 | $S \to T$ | 4 / 4 (đầy) | +4 |
| 4→3 | $T \to S$ | 0 / 9 | không |
| các cung còn lại | trong $S$ hoặc trong $T$ | – | không |
| Tổng | 23 = luồng cực đại |
Bảng 3. Lát cắt nhỏ nhất của mạng CLRS (mặc định trong mô phỏng): $S = \{1, 2, 3, 5\}$, $T = \{4, 6\}$.
Xem code C++ / Python: luồng cực đại và truy vết lát cắt nhỏ nhất (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m, s, t;
vector<int> to;
vector<long long> cap;
vector<vector<int>> adj;
vector<int> bfs(){ // par[v] = cạnh đi vào v, -1: không tới được
vector<int> par(n + 1, -1);
par[s] = -2;
queue<int> q; q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
for(int id : adj[u])
if(par[to[id]] == -1 && cap[id] > 0){ par[to[id]] = id; q.push(to[id]); }
}
return par;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> s >> t;
adj.assign(n + 1, {});
vector<int> eu(m), ev(m);
for(int i = 0; i < m; i++){
long long c;
cin >> eu[i] >> ev[i] >> c;
adj[eu[i]].push_back(to.size()); to.push_back(ev[i]); cap.push_back(c);
adj[ev[i]].push_back(to.size()); to.push_back(eu[i]); cap.push_back(0);
}
long long flow = 0;
while(true){
vector<int> par = bfs();
if(par[t] == -1) break;
long long f = LLONG_MAX;
for(int v = t; v != s; v = to[par[v] ^ 1]) f = min(f, cap[par[v]]);
for(int v = t; v != s; v = to[par[v] ^ 1]){ cap[par[v]] -= f; cap[par[v] ^ 1] += f; }
flow += f;
}
vector<int> par = bfs(); // BFS lần cuối: phía S = các đỉnh tới được
vector<int> cut;
for(int i = 0; i < m; i++)
if(par[eu[i]] != -1 && par[ev[i]] == -1) cut.push_back(i); // cung đi từ S sang T
cout << flow << "\n" << cut.size() << "\n";
for(int i : cut) cout << eu[i] << " " << ev[i] << "\n";
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, m, s, t = int(data[0]), int(data[1]), int(data[2]), int(data[3])
adj = [[] for _ in range(n + 1)]
to, cap, E = [], [], []
for i in range(m):
u, v, c = int(data[4 + 3 * i]), int(data[5 + 3 * i]), int(data[6 + 3 * i])
E.append((u, v))
adj[u].append(len(to)); to.append(v); cap.append(c)
adj[v].append(len(to)); to.append(u); cap.append(0)
def bfs(): # par[v] = cạnh đi vào v, -1: không tới được
par = [-1] * (n + 1)
par[s] = -2
q = deque([s])
while q:
u = q.popleft()
for e in adj[u]:
if par[to[e]] == -1 and cap[e] > 0:
par[to[e]] = e
q.append(to[e])
return par
flow = 0
while True:
par = bfs()
if par[t] == -1:
break
f, v = float('inf'), t
while v != s:
f = min(f, cap[par[v]]); v = to[par[v] ^ 1]
v = t
while v != s:
cap[par[v]] -= f; cap[par[v] ^ 1] += f; v = to[par[v] ^ 1]
flow += f
par = bfs() # BFS lần cuối: phía S = các đỉnh tới được
cut = [(u, v) for u, v in E if par[u] != -1 and par[v] == -1]
print(flow)
print(len(cut))
for u, v in cut:
print(u, v)
main()Phần 5Mô hình hoá: ghép cặp, đường đi rời nhau, König và Dinic
Sức mạnh thật của luồng nằm ở chỗ rất nhiều bài toán đổi được thành luồng. Kỹ năng quan trọng nhất là dựng mạng: đỉnh là gì, cung nào, dung lượng bao nhiêu.
1. Ghép cặp là một bài luồng. Thêm đỉnh phát $s$ nối tới mọi đỉnh trái (dung lượng 1), mọi đỉnh phải nối tới đỉnh thu $t$ (dung lượng 1), cạnh $L_i$–$R_j$ thành cung $L_i \to R_j$ dung lượng 1. Luồng nguyên lớn nhất chính là cặp ghép lớn nhất: dung lượng 1 ở hai đầu bảo đảm mỗi đỉnh dùng tối đa một lần. Thuật toán Kuhn thực chất là Ford–Fulkerson chạy trên mạng này, và việc “nhờ đỉnh cũ nhường chỗ” chính là đi theo cạnh ngược.
Hình 4. Ghép cặp L–R thành luồng: mọi cung (xanh: từ s và về t, tím: cạnh của đồ thị gốc) đều có dung lượng 1. Muốn mỗi người nhận tối đa $k$ việc thì đổi dung lượng $s \to L_i$ thành $k$.
Mô hình này mở rộng rất tự nhiên: mỗi người làm tối đa $a_i$ việc (cung $s \to L_i$ dung lượng $a_i$), mỗi việc cần $b_j$ người (cung $R_j \to t$ dung lượng $b_j$), hỏi có phân công đủ không (luồng có bằng $\sum b_j$ không). Kuhn không làm được những biến thể này, nhưng luồng thì làm được ngay.
2. Đường đi rời cạnh. Số đường đi từ $s$ tới $t$ nhiều nhất, đôi một không chung cạnh, bằng luồng cực đại khi mọi cung dung lượng 1 (định lý Menger). Đồ thị vô hướng thì mỗi cạnh $u$–$v$ thành cặp cạnh $u \to v$, $v \to u$ cùng dung lượng 1 và là cạnh ngược của nhau. Muốn các đường không chung đỉnh thì tách đỉnh: mỗi đỉnh $v$ thành $v_{vào} \to v_{ra}$ dung lượng 1, cung vào $v$ nối tới $v_{vào}$, cung ra khỏi $v$ đi từ $v_{ra}$.
3. Định lý König. Trên đồ thị hai phía, phủ đỉnh nhỏ nhất (chọn ít đỉnh nhất sao cho mọi cạnh có ít nhất một đầu được chọn) có kích thước bằng cặp ghép lớn nhất. Đây chính là “lát cắt nhỏ nhất = luồng lớn nhất” trên mạng Hình 4. Hệ quả: tập độc lập lớn nhất (nhiều đỉnh nhất, không hai đỉnh nào kề nhau) có $|V|$ − cặp ghép lớn nhất đỉnh. Bài “mỗi lần dọn sạch một hàng hoặc một cột” (bài tập 7) là ví dụ điển hình: hàng, cột là đỉnh, mỗi ô cần dọn là một cạnh, cần chọn ít hàng/cột nhất phủ mọi ô.
| Bước | Việc làm | Kết quả trên ví dụ |
|---|---|---|
| 1 | Tìm cặp ghép lớn nhất | L1–R2, L2–R1 (2 cặp) |
| 2 | Từ mọi đỉnh trái tự do, đi theo đường xen kẽ: trái → phải bằng cạnh chưa ghép, phải → trái bằng cạnh đã ghép | từ L3: L3 → R1 → L2; tập thăm Z = {L3, R1, L2} |
| 3 | Phủ đỉnh = (đỉnh trái không thuộc Z) ∪ (đỉnh phải thuộc Z) | {L1} ∪ {R1}: 2 đỉnh = 2 cặp |
Bảng 4. Dựng phủ đỉnh nhỏ nhất theo König trên đồ thị cạnh L1–R1, L1–R2, L2–R1, L3–R1. Chọn L1 và R1 là phủ hết 4 cạnh.
4. Phủ DAG bằng ít đường nhất. Cho đồ thị có hướng không chu trình, cần ít đường đi nhất (không chung đỉnh) sao cho mọi đỉnh nằm trên đúng một đường. Tách mỗi đỉnh thành bản “ra” (bên trái) và bản “vào” (bên phải), cung $u \to v$ thành cạnh $u_{ra}$–$v_{vào}$. Mỗi cạnh được ghép nối hai đỉnh liên tiếp trên cùng một đường, mỗi cặp ghép làm giảm số đường đi 1, nên đáp án là $n$ − cặp ghép lớn nhất (bài tập 8).
5. Thuật toán Dinic. Khi mạng lớn, Edmonds–Karp chậm vì mỗi lượt BFS chỉ đẩy một đường. Dinic cải tiến: mỗi pha BFS một lần để chia tầng (level) theo khoảng cách từ $s$, rồi dùng DFS đẩy nhiều đường cùng lúc, chỉ đi từ tầng $i$ sang tầng $i + 1$, tới khi không đẩy thêm được (gọi là luồng chặn). Mảng it[u] nhớ cạnh đang thử của $u$ để không thử lại cạnh đã “chết”. Sau mỗi pha, khoảng cách từ $s$ tới $t$ tăng ít nhất 1, nên có tối đa $V$ pha.
Xem code C++ / Python: luồng cực đại bằng dinic (đỉnh phát 1, đỉnh thu n) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> to, level, it;
vector<long long> cap;
vector<vector<int>> adj;
void addEdge(int u, int v, long long c){
adj[u].push_back(to.size()); to.push_back(v); cap.push_back(c);
adj[v].push_back(to.size()); to.push_back(u); cap.push_back(0);
}
bool bfs(int s, int t){ // chia tầng theo khoảng cách từ s
level.assign(n + 1, -1);
level[s] = 0;
queue<int> q; q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
for(int id : adj[u])
if(cap[id] > 0 && level[to[id]] < 0){ level[to[id]] = level[u] + 1; q.push(to[id]); }
}
return level[t] >= 0;
}
long long dfs(int u, int t, long long f){ // chỉ đi từ tầng i sang tầng i + 1
if(u == t) return f;
for(int &k = it[u]; k < (int)adj[u].size(); k++){
int id = adj[u][k], v = to[id];
if(cap[id] > 0 && level[v] == level[u] + 1){
long long d = dfs(v, t, min(f, cap[id]));
if(d > 0){ cap[id] -= d; cap[id ^ 1] += d; return d; }
}
}
return 0; // it[u] đã qua hết: u "chết" trong pha này
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
adj.assign(n + 1, {});
for(int i = 0; i < m; i++){
int u, v; long long c;
cin >> u >> v >> c;
addEdge(u, v, c);
}
long long flow = 0;
while(bfs(1, n)){
it.assign(n + 1, 0);
while(long long f = dfs(1, n, LLONG_MAX)) flow += f; // luồng chặn của pha
}
cout << flow;
return 0;
}import sys
from collections import deque
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
to, cap = [], []
for i in range(m):
u, v, c = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
adj[u].append(len(to)); to.append(v); cap.append(c)
adj[v].append(len(to)); to.append(u); cap.append(0)
s, t, flow, INF = 1, n, 0, float('inf')
while True:
level = [-1] * (n + 1) # chia tầng theo khoảng cách từ s
level[s] = 0
q = deque([s])
while q:
u = q.popleft()
for e in adj[u]:
if cap[e] > 0 and level[to[e]] < 0:
level[to[e]] = level[u] + 1
q.append(to[e])
if level[t] < 0:
break
it = [0] * (n + 1)
def dfs(u, f): # chỉ đi từ tầng i sang tầng i + 1
if u == t:
return f
while it[u] < len(adj[u]):
e = adj[u][it[u]]
v = to[e]
if cap[e] > 0 and level[v] == level[u] + 1:
d = dfs(v, min(f, cap[e]))
if d > 0:
cap[e] -= d; cap[e ^ 1] += d
return d
it[u] += 1
return 0
while True: # luồng chặn của pha
f = dfs(s, INF)
if f == 0:
break
flow += f
print(flow)
main()| Thuật toán | Độ phức tạp | Dùng khi |
|---|---|---|
| Kuhn | $O(VE)$ | ghép cặp hai phía, $V \le$ vài nghìn; code ngắn nhất |
| Hopcroft–Karp | $O(E\sqrt{V})$ | ghép cặp hai phía rất lớn, $V, E \sim 10^5$ |
| Edmonds–Karp | $O(VE^2)$ | luồng nhỏ, dễ cài và dễ truy lát cắt |
| Dinic | $O(V^2E)$; mạng ghép cặp: $O(E\sqrt{V})$ | mặc định khi đi thi cho mọi bài luồng |
Bảng 5. So sánh các thuật toán. Trên mạng ghép cặp (Hình 4), Dinic chạy đúng như Hopcroft–Karp. Thực tế Dinic thường nhanh hơn nhiều so với cận trên lý thuyết.
Trên blog hiện chưa có bài lời giải nào thuộc chủ đề ghép cặp và luồng. Em luyện chắc phần nền tảng là BFS trên đồ thị (dùng trong tô 2 màu, Edmonds–Karp, Dinic) qua các bài dưới đây, rồi làm 8 bài tập cuối bài.
- Covid (ICTU P58) (Trung bình)
- The Time When the Network Becomes Idle (LeetCode 2039) (Trung bình)
- Hội Chợ (Khó)
Bài tậpLuyện ghép cặp và luồng cực đại
Lớp có $n$ bạn ($n \le 10^5$) và $m$ cặp bạn hay cãi nhau ($m \le 2 \cdot 10^5$). Thầy muốn chia cả lớp thành hai đội (một đội có thể rỗng) sao cho không có hai bạn cãi nhau nào chung đội. In YES nếu chia được, NO nếu không.
4 4
1 2
2 3
3 4
4 1YES📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> color(n + 1, 0);
for(int s = 1; s <= n; s++){
if(color[s]) continue;
color[s] = 1;
queue<int> q; q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
for(int v : adj[u]){
if(!color[v]){ color[v] = 3 - color[u]; q.push(v); }
else if(color[v] == color[u]){ cout << "NO"; return 0; }
}
}
}
cout << "YES";
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v); adj[v].append(u)
color = [0] * (n + 1)
for s in range(1, n + 1):
if color[s]:
continue
color[s] = 1
q = deque([s])
while q:
u = q.popleft()
for v in adj[u]:
if not color[v]:
color[v] = 3 - color[u]; q.append(v)
elif color[v] == color[u]:
print("NO"); return
print("YES")
main()Có $n$ người và $k$ công việc ($n, k \le 200$). Cho $m$ cặp $(a, b)$ ($m \le 5000$) nghĩa là người $a$ làm được việc $b$. Mỗi người nhận tối đa một việc, mỗi việc giao cho tối đa một người. Hỏi giao được nhiều nhất bao nhiêu việc?
3 3 4
1 1
1 2
2 1
3 12📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, k, m;
vector<int> adj[205];
int matchJob[205], vis[205], stamp = 0; // matchJob[j] = người đang làm việc j
bool tryKuhn(int u){
for(int j : adj[u]){
if(vis[j] == stamp) continue;
vis[j] = stamp;
if(matchJob[j] == 0 || tryKuhn(matchJob[j])){ matchJob[j] = u; return true; }
}
return false;
}
int main(){
cin >> n >> k >> m;
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
adj[a].push_back(b);
}
int res = 0;
for(int u = 1; u <= n; u++){ stamp++; if(tryKuhn(u)) res++; }
cout << res;
return 0;
}import sys
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.buffer.read().split()
n, k, m = int(data[0]), int(data[1]), int(data[2])
adj = [[] for _ in range(n + 1)]
for i in range(m):
adj[int(data[3 + 2 * i])].append(int(data[4 + 2 * i]))
match_job = [0] * (k + 1) # match_job[j] = người đang làm việc j
vis = [0] * (k + 1)
def try_kuhn(u, stamp):
for j in adj[u]:
if vis[j] == stamp:
continue
vis[j] = stamp
if match_job[j] == 0 or try_kuhn(match_job[j], stamp):
match_job[j] = u
return True
return False
print(sum(1 for u in range(1, n + 1) if try_kuhn(u, u)))
main()Thành phố có $n$ trạm ($n \le 200$) và $m$ ống một chiều ($m \le 2000$); ống thứ $i$ dẫn nước từ trạm $u_i$ tới trạm $v_i$ với lưu lượng tối đa $c_i$ ($1 \le c_i \le 10^9$). Có thể có nhiều ống nối cùng hai trạm. Hỏi mỗi giây bơm được nhiều nhất bao nhiêu nước từ trạm 1 tới trạm $n$?
4 5
1 2 3
1 3 2
2 3 1
2 4 2
3 4 35📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> to, level, it;
vector<long long> cap;
vector<vector<int>> adj;
void addEdge(int u, int v, long long c){
adj[u].push_back(to.size()); to.push_back(v); cap.push_back(c);
adj[v].push_back(to.size()); to.push_back(u); cap.push_back(0);
}
bool bfs(int s, int t){ // chia tầng theo khoảng cách từ s
level.assign(n + 1, -1);
level[s] = 0;
queue<int> q; q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
for(int id : adj[u])
if(cap[id] > 0 && level[to[id]] < 0){ level[to[id]] = level[u] + 1; q.push(to[id]); }
}
return level[t] >= 0;
}
long long dfs(int u, int t, long long f){ // chỉ đi từ tầng i sang tầng i + 1
if(u == t) return f;
for(int &k = it[u]; k < (int)adj[u].size(); k++){
int id = adj[u][k], v = to[id];
if(cap[id] > 0 && level[v] == level[u] + 1){
long long d = dfs(v, t, min(f, cap[id]));
if(d > 0){ cap[id] -= d; cap[id ^ 1] += d; return d; }
}
}
return 0; // it[u] đã qua hết: u "chết" trong pha này
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
adj.assign(n + 1, {});
for(int i = 0; i < m; i++){
int u, v; long long c;
cin >> u >> v >> c;
addEdge(u, v, c);
}
long long flow = 0;
while(bfs(1, n)){
it.assign(n + 1, 0);
while(long long f = dfs(1, n, LLONG_MAX)) flow += f; // luồng chặn của pha
}
cout << flow;
return 0;
}import sys
from collections import deque
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
to, cap = [], []
for i in range(m):
u, v, c = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
adj[u].append(len(to)); to.append(v); cap.append(c)
adj[v].append(len(to)); to.append(u); cap.append(0)
s, t, flow, INF = 1, n, 0, float('inf')
while True:
level = [-1] * (n + 1) # chia tầng theo khoảng cách từ s
level[s] = 0
q = deque([s])
while q:
u = q.popleft()
for e in adj[u]:
if cap[e] > 0 and level[to[e]] < 0:
level[to[e]] = level[u] + 1
q.append(to[e])
if level[t] < 0:
break
it = [0] * (n + 1)
def dfs(u, f): # chỉ đi từ tầng i sang tầng i + 1
if u == t:
return f
while it[u] < len(adj[u]):
e = adj[u][it[u]]
v = to[e]
if cap[e] > 0 and level[v] == level[u] + 1:
d = dfs(v, min(f, cap[e]))
if d > 0:
cap[e] -= d; cap[e ^ 1] += d
return d
it[u] += 1
return 0
while True: # luồng chặn của pha
f = dfs(s, INF)
if f == 0:
break
flow += f
print(flow)
main()Có $n$ thành phố ($n \le 100$) và $m$ con đường hai chiều ($m \le 1000$). Đoàn xe cần đi từ thành phố 1 tới thành phố $n$ theo nhiều lộ trình khác nhau, hai lộ trình bất kỳ không được đi chung một con đường (được phép đi qua chung thành phố). Hỏi có thể chọn nhiều nhất bao nhiêu lộ trình?
4 5
1 2
1 3
2 3
2 4
3 42📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> to;
vector<long long> cap;
vector<vector<int>> adj(n + 1);
for(int i = 0; i < m; i++){
int u, v; long long c = 1;
cin >> u >> v;
adj[u].push_back(to.size()); to.push_back(v); cap.push_back(c); // u -> v
adj[v].push_back(to.size()); to.push_back(u); cap.push_back(c); // v -> u, cũng dung lượng c
}
long long flow = 0;
while(true){
vector<int> par(n + 1, -1);
par[1] = -2;
queue<int> q; q.push(1);
while(!q.empty() && par[n] == -1){
int u = q.front(); q.pop();
for(int id : adj[u])
if(par[to[id]] == -1 && cap[id] > 0){ par[to[id]] = id; q.push(to[id]); }
}
if(par[n] == -1) break;
long long f = LLONG_MAX;
for(int v = n; v != 1; v = to[par[v] ^ 1]) f = min(f, cap[par[v]]);
for(int v = n; v != 1; v = to[par[v] ^ 1]){ cap[par[v]] -= f; cap[par[v] ^ 1] += f; }
flow += f;
}
cout << flow;
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
to, cap = [], []
pos = 2
for _ in range(m):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
c = 1
adj[u].append(len(to)); to.append(v); cap.append(c) # u -> v
adj[v].append(len(to)); to.append(u); cap.append(c) # v -> u, cũng dung lượng c
flow = 0
while True:
par = [-1] * (n + 1)
par[1] = -2
q = deque([1])
while q and par[n] == -1:
u = q.popleft()
for e in adj[u]:
if par[to[e]] == -1 and cap[e] > 0:
par[to[e]] = e
q.append(to[e])
if par[n] == -1:
break
f, v = float('inf'), n
while v != 1:
f = min(f, cap[par[v]]); v = to[par[v] ^ 1]
v = n
while v != 1:
cap[par[v]] -= f; cap[par[v] ^ 1] += f; v = to[par[v] ^ 1]
flow += f
print(flow)
main()Có $n$ đồn ($n \le 100$) và $m$ con đường hai chiều ($m \le 1000$); phá con đường thứ $i$ tốn $c_i$ ($1 \le c_i \le 10^9$). Tìm tổng chi phí nhỏ nhất để phá một số đường sao cho từ đồn 1 không còn đi được tới đồn $n$.
4 5
1 2 5
1 3 4
2 3 1
2 4 2
3 4 67📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> to;
vector<long long> cap;
vector<vector<int>> adj(n + 1);
for(int i = 0; i < m; i++){
int u, v; long long c;
cin >> u >> v >> c;
adj[u].push_back(to.size()); to.push_back(v); cap.push_back(c); // u -> v
adj[v].push_back(to.size()); to.push_back(u); cap.push_back(c); // v -> u, cũng dung lượng c
}
long long flow = 0;
while(true){
vector<int> par(n + 1, -1);
par[1] = -2;
queue<int> q; q.push(1);
while(!q.empty() && par[n] == -1){
int u = q.front(); q.pop();
for(int id : adj[u])
if(par[to[id]] == -1 && cap[id] > 0){ par[to[id]] = id; q.push(to[id]); }
}
if(par[n] == -1) break;
long long f = LLONG_MAX;
for(int v = n; v != 1; v = to[par[v] ^ 1]) f = min(f, cap[par[v]]);
for(int v = n; v != 1; v = to[par[v] ^ 1]){ cap[par[v]] -= f; cap[par[v] ^ 1] += f; }
flow += f;
}
cout << flow;
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
to, cap = [], []
pos = 2
for _ in range(m):
u, v = int(data[pos]), int(data[pos + 1]); pos += 2
c = int(data[pos]); pos += 1
adj[u].append(len(to)); to.append(v); cap.append(c) # u -> v
adj[v].append(len(to)); to.append(u); cap.append(c) # v -> u, cũng dung lượng c
flow = 0
while True:
par = [-1] * (n + 1)
par[1] = -2
q = deque([1])
while q and par[n] == -1:
u = q.popleft()
for e in adj[u]:
if par[to[e]] == -1 and cap[e] > 0:
par[to[e]] = e
q.append(to[e])
if par[n] == -1:
break
f, v = float('inf'), n
while v != 1:
f = min(f, cap[par[v]]); v = to[par[v] ^ 1]
v = n
while v != 1:
cap[par[v]] -= f; cap[par[v] ^ 1] += f; v = to[par[v] ^ 1]
flow += f
print(flow)
main()Cho bảng $n \times m$ ($n, m \le 30$), ô . là ô trống, ô # là ô bị chặn. Đặt các viên domino $1 \times 2$ (nằm ngang hoặc dọc) lên các ô trống, hai viên không chồng nhau. Hỏi đặt được nhiều nhất bao nhiêu viên?
3 3
...
.#.
...4📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<string> g;
vector<int> adj[1005]; // ô đen (i + j chẵn) -> các ô trắng kề
int matchW[1005], vis[1005], stamp = 0;
bool tryKuhn(int u){
for(int w : adj[u]){
if(vis[w] == stamp) continue;
vis[w] = stamp;
if(matchW[w] == -1 || tryKuhn(matchW[w])){ matchW[w] = u; return true; }
}
return false;
}
int main(){
cin >> n >> m;
g.resize(n);
for(auto &row : g) cin >> row;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
if(g[i][j] == '#' || (i + j) % 2) continue;
for(int d = 0; d < 4; d++){
int x = i + dx[d], y = j + dy[d];
if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.') adj[i * m + j].push_back(x * m + y);
}
}
memset(matchW, -1, sizeof(matchW));
int res = 0;
for(int u = 0; u < n * m; u++)
if(!adj[u].empty()){ stamp++; if(tryKuhn(u)) res++; }
cout << res;
return 0;
}import sys
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
adj = {} # ô đen (i + j chẵn) -> các ô trắng kề
for i in range(n):
for j in range(m):
if g[i][j] == '#' or (i + j) % 2:
continue
nb = []
for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= x < n and 0 <= y < m and g[x][y] == '.':
nb.append(x * m + y)
if nb:
adj[i * m + j] = nb
match_w = [-1] * (n * m)
vis = [0] * (n * m)
def try_kuhn(u, stamp):
for w in adj[u]:
if vis[w] == stamp:
continue
vis[w] = stamp
if match_w[w] == -1 or try_kuhn(match_w[w], stamp):
match_w[w] = u
return True
return False
res = 0
for k, u in enumerate(adj):
if try_kuhn(u, k + 1):
res += 1
print(res)
main()Sân trường là bảng $n \times m$ ($n, m \le 100$), ô * có rác, ô . sạch. Mỗi lượt, robot dọn sạch cả một hàng hoặc cả một cột. Hỏi cần ít nhất bao nhiêu lượt để sân sạch hết?
3 4
*.*.
.*..
.*..2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> adj[105]; // hàng i -> các cột có rác ở hàng i
int matchCol[105], vis[105], stamp = 0;
bool tryKuhn(int r){
for(int c : adj[r]){
if(vis[c] == stamp) continue;
vis[c] = stamp;
if(matchCol[c] == 0 || tryKuhn(matchCol[c])){ matchCol[c] = r; return true; }
}
return false;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
string s;
cin >> s;
for(int j = 1; j <= m; j++) if(s[j - 1] == '*') adj[i].push_back(j); // ô rác = cạnh (hàng, cột)
}
int res = 0;
for(int i = 1; i <= n; i++){ stamp++; if(tryKuhn(i)) res++; }
cout << res; // König: phủ đỉnh nhỏ nhất = ghép cặp lớn nhất
return 0;
}import sys
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
adj = [[j + 1 for j, ch in enumerate(data[2 + i]) if ch == '*'] for i in range(n)]
match_col = [0] * (m + 1)
vis = [0] * (m + 1)
def try_kuhn(r, stamp): # r: chỉ số hàng (đếm từ 1)
for c in adj[r - 1]:
if vis[c] == stamp:
continue
vis[c] = stamp
if match_col[c] == 0 or try_kuhn(match_col[c], stamp):
match_col[c] = r
return True
return False
print(sum(1 for r in range(1, n + 1) if try_kuhn(r, r))) # König
main()Nhà kho có $n$ trạm ($n \le 300$) nối bởi $m$ băng chuyền một chiều ($m \le 5000$), không có vòng tròn khép kín (đồ thị DAG). Mỗi robot xuất phát ở một trạm bất kỳ, đi theo các băng chuyền và dừng ở một trạm bất kỳ. Mỗi trạm phải được đúng một robot đi qua. Hỏi cần ít nhất bao nhiêu robot?
5 4
1 2
2 3
1 4
4 52📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> adj[305]; // bản "ra" của u -> bản "vào" của v
int matchIn[305], vis[305], stamp = 0;
bool tryKuhn(int u){
for(int v : adj[u]){
if(vis[v] == stamp) continue;
vis[v] = stamp;
if(matchIn[v] == 0 || tryKuhn(matchIn[v])){ matchIn[v] = u; return true; }
}
return false;
}
int main(){
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
int match = 0;
for(int u = 1; u <= n; u++){ stamp++; if(tryKuhn(u)) match++; }
cout << n - match; // mỗi cặp ghép nối hai đoạn đường thành một
return 0;
}import sys
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)] # bản "ra" của u -> bản "vào" của v
for i in range(m):
adj[int(data[2 + 2 * i])].append(int(data[3 + 2 * i]))
match_in = [0] * (n + 1)
vis = [0] * (n + 1)
def try_kuhn(u, stamp):
for v in adj[u]:
if vis[v] == stamp:
continue
vis[v] = stamp
if match_in[v] == 0 or try_kuhn(match_in[v], stamp):
match_in[v] = u
return True
return False
match = sum(1 for u in range(1, n + 1) if try_kuhn(u, u))
print(n - match) # mỗi cặp ghép nối hai đoạn đường thành một
main()
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét