Cây Gomory-Hu
Mọi đồ thị vô hướng có một cây trọng số mà luồng cực đại giữa hai đỉnh bất kỳ bằng cạnh nhỏ nhất trên đường đi trong cây; thuật toán Gusfield dựng cây này bằng n - 1 lần luồng cực đại, không cần co đỉnh.
Cây Gomory-Hu của một đồ thị vô hướng có trọng số (trọng số là sức chứa) là một cây trên cùng tập đỉnh, mỗi cạnh có trọng số, sao cho với mọi cặp đỉnh :
trong đó là luồng cực đại (bằng lát cắt nhỏ nhất) giữa và trong . Hơn nữa, bỏ cạnh nhỏ nhất đó khỏi thì hai thành phần thu được chính là một lát cắt nhỏ nhất của giữa và .
Ý nghĩa: thay vì lần luồng cực đại để trả lời mọi cặp, chỉ cần lần để dựng cây, sau đó mỗi truy vấn là một bài "cạnh nhỏ nhất trên đường đi trong cây". Với vài trăm và Dinic, đây là cách chuẩn cho các bài "tính luồng cực đại / lát cắt nhỏ nhất giữa mọi cặp đỉnh", "tổng trên mọi cặp", hay "kiểm tra một ma trận có phải ma trận luồng hay không".
Ý tưởng / Trực giác
Tính chất bất đẳng thức tam giác kiểu min. Với mọi :
Lý do: xét lát cắt nhỏ nhất tách khỏi . Đỉnh nằm ở một phía, giả sử phía của ; khi đó lát cắt này cũng tách khỏi , nên . Lặp lại cho một dãy đỉnh: các trên mọi dãy . Vậy hàm có tính chất "siêu mêtric", và một hàm như vậy luôn được biểu diễn bằng cây khung lớn nhất của đồ thị đầy đủ với trọng số : chỉ có tối đa giá trị khác nhau.
Lát cắt không chéo nhau. Điều khó là chứng minh tồn tại một cây mà các lát cắt ứng với cạnh cây đều là lát cắt nhỏ nhất thật trong . Gomory và Hu dùng tính chất dưới modular của hàm lát cắt (tổng sức chứa các cạnh rời ):
để chỉ ra rằng luôn chọn được các lát cắt nhỏ nhất lồng nhau hoặc rời nhau (không chéo). Một họ lát cắt không chéo nhau trên đỉnh có đúng cấu trúc cây.
Thuật toán Gusfield (không co đỉnh). Thuật toán gốc của Gomory-Hu phải co các nhóm đỉnh thành siêu đỉnh. Gusfield (1990) chỉ ra một cách đơn giản hơn nhiều, mọi lần tính luồng đều trên đồ thị gốc, cho ra một cây tương đương luồng (equivalent flow tree) với cùng tính chất về giá trị :
- Đánh số đỉnh . Ban đầu
par[i] = 0với mọi . - Với :
- Gọi =
par[s]. Tính luồng cực đại giữa và trên , đặtw[s] = f. - Lấy phía của lát cắt nhỏ nhất: các đỉnh còn đến được từ trong đồ thị thặng dư.
- Với mọi có
par[i] == tvà : đặtpar[i] = s.
- Gọi =
- Cây gồm các cạnh trọng số
w[i].
Trực giác: tại bước , các đỉnh "đang treo" dưới được chia làm hai nhóm theo lát cắt vừa tìm, nhóm cùng phía với chuyển sang treo dưới . Đó là phép chia nhóm của Gomory-Hu, chỉ là không cần co đỉnh vì lát cắt nhỏ nhất luôn có thể chọn không chéo các lát cắt đã chọn trước đó.
Ví dụ chạy tay
Đồ thị đỉnh, cạnh (số trên cạnh là sức chứa):
graph 0 1 3 0 2 2 1 2 1 1 3 4 2 3 2 2 4 3 3 4 1
Cạnh: - (3), - (2), - (1), - (4), - (2), - (3), - (1).
Chạy Gusfield (par ban đầu là ):
| = par[s] | phía của lát cắt | par sau bước | ||
|---|---|---|---|---|
| 1 | 0 | 5 | ||
| 2 | 1 | 6 | ||
| 3 | 1 | 7 | ||
| 4 | 2 | 4 |
Kiểm tra từng lát cắt: bước 1 tách , cắt - và -, tổng . Bước 2 tách , cắt -, -, -, -, tổng . Bước 3 tách : . Bước 4 tách : .
Cây thu được:
tree 0 1 5 1 2 6 1 3 7 2 4 4
Ma trận luồng cực đại đọc từ cây (cạnh nhỏ nhất trên đường đi):
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 5 | 5 | 5 | 4 |
| 1 | 5 | 0 | 6 | 7 | 4 |
| 2 | 5 | 6 | 0 | 6 | 4 |
| 3 | 5 | 7 | 6 | 0 | 4 |
| 4 | 4 | 4 | 4 | 4 | 0 |
Ví dụ : đường đi có các cạnh , nhỏ nhất là . Lát cắt toàn cục nhỏ nhất của đồ thị là cạnh nhỏ nhất của cây, bằng .
Cài đặt
Chương trình đọc , và cạnh vô hướng u v c (đỉnh từ ), dựng cây bằng Gusfield với Dinic, rồi in ma trận bằng một lần duyệt cây từ mỗi đỉnh. Phía của lát cắt lấy từ mảng level của lần BFS cuối cùng trong Dinic (lần BFS không tới được ).
#include <bits/stdc++.h>
using namespace std;
struct Dinic {
struct Edge {
int to;
long long cap, orig;
};
int n;
vector<Edge> e;
vector<vector<int>> g;
vector<int> level, it;
Dinic(int n) : n(n), g(n), level(n), it(n) {}
// Cạnh vô hướng u - v sức chứa c: hai cung ngược chiều, mỗi cung sức chứa c
void add_undirected(int u, int v, long long c) {
g[u].push_back(e.size());
e.push_back({v, c, c});
g[v].push_back(e.size());
e.push_back({u, c, c});
}
void reset() {
for (auto& x : e) x.cap = x.orig; // khôi phục sức chứa trước mỗi lần tính luồng
}
bool bfs(int s, int t) {
fill(level.begin(), level.end(), -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int id : g[u])
if (e[id].cap > 0 && level[e[id].to] < 0) {
level[e[id].to] = level[u] + 1;
q.push(e[id].to);
}
}
return level[t] >= 0;
}
long long dfs(int u, int t, long long f) {
if (u == t) return f;
for (int& i = it[u]; i < (int)g[u].size(); i++) {
Edge& ed = e[g[u][i]];
if (ed.cap > 0 && level[ed.to] == level[u] + 1) {
long long d = dfs(ed.to, t, min(f, ed.cap));
if (d > 0) {
ed.cap -= d;
e[g[u][i] ^ 1].cap += d;
return d;
}
}
}
return 0;
}
long long maxflow(int s, int t) {
reset();
long long flow = 0;
while (bfs(s, t)) {
fill(it.begin(), it.end(), 0);
while (long long f = dfs(s, t, LLONG_MAX)) flow += f;
}
return flow;
}
// Sau maxflow: đỉnh u thuộc phía s của lát cắt nhỏ nhất khi level[u] >= 0
bool on_s_side(int u) { return level[u] >= 0; }
};
// Gusfield: dựng cây Gomory-Hu (cây tương đương luồng) bằng n - 1 lần luồng cực đại.
// Trả về par[i], w[i]: cạnh cây (i, par[i]) có trọng số w[i], với i = 1..n-1, gốc là 0.
void gomory_hu(int n, Dinic& D, vector<int>& par, vector<long long>& w) {
par.assign(n, 0);
w.assign(n, 0);
for (int s = 1; s < n; s++) {
int t = par[s];
w[s] = D.maxflow(s, t);
for (int i = s + 1; i < n; i++) // đỉnh sau s cùng phía s và cùng cha t: đổi cha
if (par[i] == t && D.on_s_side(i)) par[i] = s;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
Dinic D(n);
for (int i = 0; i < m; i++) {
int u, v;
long long c;
cin >> u >> v >> c; // đỉnh đánh số từ 0
D.add_undirected(u, v, c);
}
vector<int> par;
vector<long long> w;
gomory_hu(n, D, par, w);
// Luồng cực đại giữa u, v = cạnh nhỏ nhất trên đường đi u - v trong cây.
// Tính cả ma trận bằng DFS từ mỗi đỉnh trên cây: O(n^2).
vector<vector<pair<int, long long>>> tree(n);
for (int i = 1; i < n; i++) {
tree[i].push_back({par[i], w[i]});
tree[par[i]].push_back({i, w[i]});
}
for (int src = 0; src < n; src++) {
vector<long long> best(n, -1);
best[src] = LLONG_MAX;
vector<int> st = {src};
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (auto [v, c] : tree[u])
if (best[v] < 0) {
best[v] = min(best[u], c);
st.push_back(v);
}
}
for (int v = 0; v < n; v++) cout << (v == src ? 0 : best[v]) << (v + 1 < n ? ' ' : '\n');
}
}
import sys
from collections import deque
class Dinic:
def __init__(self, n):
self.n = n
self.to, self.cap, self.orig = [], [], []
self.g = [[] for _ in range(n)]
self.level = [0] * n
# Cạnh vô hướng u - v sức chứa c: hai cung ngược chiều, mỗi cung sức chứa c
def add_undirected(self, u, v, c):
for a, b in ((u, v), (v, u)):
self.g[a].append(len(self.to))
self.to.append(b)
self.cap.append(c)
self.orig.append(c)
def bfs(self, s, t):
level = [-1] * self.n
level[s] = 0
q = deque([s])
while q:
u = q.popleft()
for i in self.g[u]:
if self.cap[i] > 0 and level[self.to[i]] < 0:
level[self.to[i]] = level[u] + 1
q.append(self.to[i])
self.level = level
return level[t] >= 0
def dfs(self, u, t, f, it):
if u == t:
return f
g, to, cap, level = self.g[u], self.to, self.cap, self.level
while it[u] < len(g):
i = g[it[u]]
v = to[i]
if cap[i] > 0 and level[v] == level[u] + 1:
d = self.dfs(v, t, min(f, cap[i]), it)
if d > 0:
cap[i] -= d
cap[i ^ 1] += d
return d
it[u] += 1
return 0
def maxflow(self, s, t):
self.cap = self.orig[:] # khôi phục sức chứa trước mỗi lần tính luồng
flow = 0
while self.bfs(s, t):
it = [0] * self.n
f = self.dfs(s, t, float("inf"), it)
while f > 0:
flow += f
f = self.dfs(s, t, float("inf"), it)
return flow
# Sau maxflow: đỉnh u thuộc phía s của lát cắt nhỏ nhất khi level[u] >= 0
def on_s_side(self, u):
return self.level[u] >= 0
# Gusfield: dựng cây Gomory-Hu (cây tương đương luồng) bằng n - 1 lần luồng cực đại.
# Trả về par, w: cạnh cây (i, par[i]) có trọng số w[i], với i = 1..n-1, gốc là 0.
def gomory_hu(n, D):
par, w = [0] * n, [0] * n
for s in range(1, n):
t = par[s]
w[s] = D.maxflow(s, t)
for i in range(s + 1, n): # đỉnh sau s cùng phía s và cùng cha t: đổi cha
if par[i] == t and D.on_s_side(i):
par[i] = s
return par, w
def main():
sys.setrecursionlimit(10000)
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
D = Dinic(n)
for i in range(m):
u, v, c = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
D.add_undirected(u, v, c) # đỉnh đánh số từ 0
par, w = gomory_hu(n, D)
# Luồng cực đại giữa u, v = cạnh nhỏ nhất trên đường đi u - v trong cây.
tree = [[] for _ in range(n)]
for i in range(1, n):
tree[i].append((par[i], w[i]))
tree[par[i]].append((i, w[i]))
out = []
for src in range(n):
best = [-1] * n
best[src] = float("inf")
st = [src]
while st:
u = st.pop()
for v, c in tree[u]:
if best[v] < 0:
best[v] = min(best[u], c)
st.append(v)
best[src] = 0
out.append(" ".join(map(str, best)))
print("\n".join(out))
main()
Bản Python dùng DFS đệ quy trong Dinic nên chỉ hợp với đồ thị nhỏ (độ sâu BFS vừa phải); với vài trăm và nhiều cạnh nên dùng C++.
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
| Dựng cây (Gusfield) | , với Dinic xấu nhất | |
Cập nhật par sau mỗi lần luồng |
, tổng | |
| Ma trận cho mọi cặp | (duyệt cây từ mỗi đỉnh) | nếu lưu |
| Một truy vấn | với nâng nhị phân trên cây | |
| Tổng trên mọi cặp | : thêm cạnh cây theo trọng số giảm dần vào DSU, cạnh nối hai nhóm cỡ đóng góp |
Vì sao chỉ cần lần luồng? Mỗi đỉnh tính đúng một lần luồng với cha hiện tại của nó, và mỗi lần cho đúng một cạnh của cây. Mọi giá trị khác suy ra từ cây nhờ tính chất .
⚠️ Lỗi thường gặp
- Không khôi phục sức chứa trước mỗi lần luồng: Gusfield chạy luồng trên đồ thị gốc mỗi lần. Dùng lại đồ thị thặng dư của lần trước cho đáp án sai mà không báo lỗi gì.
- Lấy sai phía lát cắt: phía là các đỉnh đến được từ trong đồ thị thặng dư sau khi luồng đã cực đại (lần BFS cuối, không tới được ). Dùng
levelcủa một lần BFS giữa chừng, hoặc lấy phía của , đều làm cây sai. - Áp dụng cho đồ thị có hướng: cây Gomory-Hu chỉ tồn tại cho đồ thị vô hướng (hàm phải đối xứng). Với đồ thị có hướng, nói chung và không có cấu trúc cây.
- Cộng sức chứa hai lần: nếu đề cho ma trận đối xứng , chỉ thêm một cạnh vô hướng cho mỗi cặp (hai cung ngược chiều, mỗi cung sức chứa ). Thêm cạnh cho cả và là nhân đôi sức chứa.
- Quên đồ thị không liên thông: khi và không liên thông, luồng bằng và phía là cả thành phần của ; thuật toán vẫn đúng và cây có cạnh trọng số . Đừng bỏ qua cạnh khi trả lời truy vấn.
- Dùng cây để khôi phục lát cắt cụ thể giữa : với cây Gusfield, giá trị luôn đúng, nhưng muốn có chính tập đỉnh của lát cắt thì phải lưu lại phía ở bước sinh ra cạnh nhỏ nhất (hoặc tính lại một lần luồng giữa hai đầu cạnh đó).
Biến thể / Mở rộng
- Kiểm tra ma trận luồng: một ma trận đối xứng là ma trận luồng cực đại của một đồ thị vô hướng khi và chỉ khi nó được biểu diễn bởi cây khung lớn nhất của đồ thị đầy đủ trọng số : dựng cây khung lớn nhất rồi so cạnh nhỏ nhất trên đường đi với . Xem Cây khung nhỏ nhất (MST) (đảo dấu trọng số).
- Lát cắt toàn cục nhỏ nhất: cạnh nhỏ nhất của cây Gomory-Hu là lát cắt nhỏ nhất của cả đồ thị. Nếu chỉ cần giá trị này, thuật toán Stoer-Wagner không cần luồng.
- Tổng hoặc đếm theo : sắp các cạnh cây theo trọng số giảm dần rồi hợp nhất bằng DSU, giống Kruskal, để tính hay đếm số cặp có .
- Luồng cực đại nền tảng: cài đặt và chứng minh định lý luồng cực đại, lát cắt nhỏ nhất xem Max Flow (Dinic). Với đồ thị phẳng, từng lần luồng có thể thay bằng đường đi ngắn nhất trên đồ thị đối ngẫu.
Bài tập luyện
- Hệ thống đám mây DUT (icpc21mta): (Very Hard) Cho một ma trận , dựng một mạng cáp có đúng ma trận luồng cực đại giữa mọi cặp là hoặc báo không tồn tại. Theo định lý Gomory-Hu chỉ cần kiểm tra cây khung lớn nhất của và in chính cây đó.
- Hệ thống đám mây (icpc21mna): (Very Hard) Tính ma trận luồng cực đại giữa mọi cặp máy chủ của một mạng vô hướng với . Dựng cây bằng Gusfield với lần Dinic rồi điền ma trận từ cây.- Chiến tranh (prevoi25_war): (Expert) Kinh phí ít nhất để hai thành phố không gặp được nhau là lát cắt nhỏ nhất ; cần lát cắt nhỏ nhất toàn cục và tổng trên mọi cặp, cả hai đọc được từ cây Gomory-Hu (cạnh nhỏ nhất, và gộp cạnh cây theo trọng số giảm dần bằng DSU).
Bình luận