Hướng dẫn giải của Luồng cực đại trên mạng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm luồng cực đại từ nguồn s đến đỉnh thu t trong một đồ thị có hướng với dung lượng (sức chứa) các cung là số nguyên dương. Luồng cực đại là lượng luồng tối đa có thể đẩy từ s đến t sao cho lưu lượng trên mỗi cung không vượt quá dung lượng của nó và tại mỗi đỉnh (ngoại trừ s và t), tổng luồng vào bằng tổng luồng ra. Dữ liệu đầu vào gồm n đỉnh, m cung, và các thông số cung. Kết quả cần trả về là một số nguyên thể hiện giá trị luồng cực đại.
Các cách tiếp cận
Cách Dinic's Algorithm
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
struct Edge {
int v;
long long cap, flow;
Edge(int _v, long long _cap) : v(_v), cap(_cap), flow(0) {}
};
vector<Edge> edges;
vector<vector<int>> adj;
vector<int> level, ptr;
int n, m, s, t;
void add_edge(int u, int v, long long cap) {
adj[u].push_back(edges.size());
edges.push_back(Edge(v, cap));
adj[v].push_back(edges.size());
edges.push_back(Edge(u, 0));
}
bool bfs() {
fill(level.begin(), level.end(), -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 (edges[id].cap - edges[id].flow > 0 && level[edges[id].v] == -1) {
level[edges[id].v] = level[u] + 1;
q.push(edges[id].v);
}
}
}
return level[t] != -1;
}
long long dfs(int u, long long pushed) {
if (pushed == 0) return 0;
if (u == t) return pushed;
for (int& cid = ptr[u]; cid < adj[u].size(); ++cid) {
int id = adj[u][cid];
int v = edges[id].v;
if (level[u] + 1 != level[v] || edges[id].cap - edges[id].flow == 0) continue;
long long tr = dfs(v, min(pushed, edges[id].cap - edges[id].flow));
if (tr == 0) continue;
edges[id].flow += tr;
edges[id^1].flow -= tr;
return tr;
}
return 0;
}
long long dinic() {
long long max_flow = 0;
while (bfs()) {
fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, INF)) {
max_flow += pushed;
}
}
return max_flow;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (cin >> n >> m >> s >> t) {
adj.resize(n + 1);
level.resize(n + 1);
ptr.resize(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
long long c;
cin >> u >> v >> c;
add_edge(u, v, c);
}
cout << dinic() << endl;
}
return 0;
}
- Time Complexity: O(V^2 * E) trong trường hợp chung, hiệu quả trên thực tế thường tốt hơn (khoảng O(E sqrt(V)) cho đồ thị đơn). Với n=1200, m=120000, đây là lựa chọn tốt.
- Space Complexity: O(V + E)
Dinic's Algorithm hoạt động dựa trên việc xây dựng các đồ thị cấp độ (level graph) và tìm các luồng tăng trưởng (blocking flow) trên đó. Các bước chính:
- BFS để xây dựng Level Graph: Tìm đường đi ngắn nhất (theo số cạnh) từ nguồn s đến các đỉnh khác. Chỉ các cung có dung lượng dư thừa (cap - flow > 0) và nối từ level này sang level kia (level[v] = level[u] + 1) mới được dùng. Nếu không thể đến t, thuật toán kết thúc.
- DFS để tìm Blocking Flow: Dùng đệ quy để đẩy luồng qua các cung trong đồ thị cấp độ. Sử dụng mảng
ptrđể tối ưu, đảm bảo mỗi cạnh chỉ được xét một lần trong mỗi giai đoạn tìm luồng. - Lặp lại quá trình trên cho đến khi không còn đường đi tăng trưởng. Độ phức tạp O(V^2*E) là do có tối đa V lần BFS và mỗi lần BFS, DFS có thể tìm đến V đơn vị luồng, mỗi đơn vị tốn O(E). Tuy nhiên, với cơ chế Level Graph, số lần lặp thường ít hơn đáng kể.
Cách Edmonds-Karp Algorithm
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int MAXN = 1205;
long long capacity[MAXN][MAXN];
long long flow[MAXN][MAXN];
int parent[MAXN];
int n, m, s, t;
vector<int> adj[MAXN];
bool bfs() {
memset(parent, -1, sizeof(parent));
queue<int> q;
q.push(s);
parent[s] = s;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (parent[v] == -1 && capacity[u][v] - flow[u][v] > 0) {
parent[v] = u;
if (v == t) return true;
q.push(v);
}
}
}
return false;
}
long long edmonds_karp() {
long long max_flow = 0;
while (bfs()) {
long long path_flow = INF;
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
path_flow = min(path_flow, capacity[u][v] - flow[u][v]);
}
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
flow[u][v] += path_flow;
flow[v][u] -= path_flow;
}
max_flow += path_flow;
}
return max_flow;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (cin >> n >> m >> s >> t) {
for (int i = 0; i < m; ++i) {
int u, v;
long long c;
cin >> u >> v >> c;
adj[u].push_back(v);
adj[v].push_back(u);
capacity[u][v] += c;
}
cout << edmonds_karp() << endl;
}
return 0;
}
- Time Complexity: O(V * E^2) hoặc O(V * E * F), trong đó F là giá trị luồng cực đại. Với n=1200, m=120000, độ phức tạp này có thể quá chậm.
- Space Complexity: O(V^2) nếu dùng ma trận kề, hoặc O(V + E) nếu dùng danh sách kề và map.
Thuật toán Edmonds-Karp là một cách cài đặt đơn giản của Ford-Fulkerson sử dụng BFS để tìm đường tăng trưởng ngắn nhất (theo số cạnh) trong đồ thị dư thừa.
- Khởi tạo luồng bằng 0.
- Trong khi có đường đi từ s đến t trong đồ thị dư thừa: a. Dùng BFS để tìm đường đi ngắn nhất. b. Tính dung lượng tối thiểu (bottleneck) trên đường đi đó. c. Cập nhật dung lượng các cung trên đường đi (giảm dung lượng cung thuận, tăng dung lượng cung ngược).
- Tổng dung lượng các đường đi tìm được chính là luồng cực đại. Thuật toán này đảm bảo mỗi cạnh được xét tối đa O(V) lần, tổng cộng O(V * E). Tuy nhiên, do BFS tìm đường ngẫu nhiên (chỉ ngắn nhất về số cạnh), thuật toán có thể chạy chậm trên các đồ thị lớn hoặc có nhiều luồng nhỏ.
Cách Push-Relabel (Highest Label Version)
// Code mẫu cho Push-Relabel (HLPP)
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int MAXN = 1205;
struct Edge {
int to, rev;
long long cap;
};
vector<Edge> adj[MAXN];
long long ex[MAXN];
int ht[MAXN];
int cnt[MAXN * 2];
int n, m, s, t;
void add_edge(int u, int v, long long cap) {
Edge a = {v, (int)adj[v].size(), cap};
Edge b = {u, (int)adj[u].size(), 0};
adj[u].push_back(a);
adj[v].push_back(b);
}
void push(int u, Edge &e) {
long long d = min(ex[u], e.cap);
ex[u] -= d;
ex[e.to] += d;
e.cap -= d;
adj[e.to][e.rev].cap += d;
}
void relabel(int u) {
int min_h = 2 * n;
for (auto &e : adj[u]) {
if (e.cap > 0 && ht[e.to] < min_h) {
min_h = ht[e.to];
}
}
if (min_h < 2 * n) {
cnt[ht[u]]--;
ht[u] = min_h + 1;
cnt[ht[u]]++;
}
}
long long hlpp() {
fill(ht, ht + n + 1, 0);
fill(ex, ex + n + 1, 0);
fill(cnt, cnt + 2 * n + 1, 0);
// Khởi tạo preflow
ht[s] = n;
for (auto &e : adj[s]) {
if (e.cap > 0) {
ex[e.to] += e.cap;
adj[e.to][e.rev].cap += e.cap;
e.cap = 0;
}
}
// Tạo danh sách các đỉnh active có excess > 0 (trừ s, t)
queue<int> q;
for (int i = 1; i <= n; i++) {
if (i != s && i != t && ex[i] > 0) q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
// Push các cung có thể
for (auto &e : adj[u]) {
if (e.cap > 0 && ht[u] == ht[e.to] + 1) {
push(u, e);
}
}
if (ex[u] > 0) {
if (cnt[ht[u]] == 0) {
// Gap heuristic: nếu không có đỉnh nào ở độ cao này, reset độ cao các đỉnh >= ht[u]
for (int i = 1; i <= n; i++) {
if (i != s && i != t && ht[i] > ht[u]) {
cnt[ht[i]]--;
ht[i] = 2 * n + 1; // Đặt lên độ cao vô cực
}
}
}
relabel(u);
q.push(u);
}
}
return ex[t];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (cin >> n >> m >> s >> t) {
for (int i = 0; i < m; ++i) {
int u, v;
long long c;
cin >> u >> v >> c;
add_edge(u, v, c);
}
cout << hlpp() << endl;
}
return 0;
}
- Time Complexity: O(V^2 * sqrt(E)) hoặc O(V^3) depending on implementation. Rất nhanh trên thực tế, đặc biệt với số lượng cung lớn.
- Space Complexity: O(V + E)
Push-Relabel là thuật toán tìm luồng cực đại hiệu quả cao, khác biệt với Ford-Fulkerson/Dinic ở chỗ nó không cần tìm đường đi hoàn chỉnh từ nguồn đến đích. Thay vào đó, nó duy trì một "preflow" (luồng thô) và thực hiện các thao tác Push (đẩy luồng) và Relabel (nâng độ cao) để đảm bảo điều kiện độ cao.
- Khởi tạo: Đặt độ cao của nguồn s bằng V (số đỉnh). Đẩy luồng từ s đến tất cả hàng xóm, thiết lập luồng ngược.
- Vòng lặp chính: Chọn một đỉnh "active" (có lượng thừa > 0, không phải s hay t).
- Push: Nếu có cung nối đến đỉnh có độ cao thấp hơn 1单位, đẩy lượng thừa tối đa.
- Relabel: Nếu không thể đẩy, nâng độ cao của đỉnh lên 1 đơn vị so với độ cao thấp nhất của hàng xóm.
- Khi không còn đỉnh active nào (ngoại trừ s và t), luồng tại đỉnh thu t chính là luồng cực đại. Phiên bản Highest Label (HLPP) ưu tiên các đỉnh có độ cao lớn hơn, giúp giảm độ phức tạp xuống O(V^3) hoặc O(V^2 sqrt(E)).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(V^2 * E) trong trường hợp chung, hiệu quả trên thực tế thường tốt hơn (khoảng O(E sqrt(V)) cho đồ thị đơn). Với n=1200, m=120000, đây là lựa chọn tốt. | O(V + E) | Dinic's Algorithm |
| 2 | O(V * E^2) hoặc O(V * E * F), trong đó F là giá trị luồng cực đại. Với n=1200, m=120000, độ phức tạp này có thể quá chậm. | O(V^2) nếu dùng ma trận kề, hoặc O(V + E) nếu dùng danh sách kề và map. | Edmonds-Karp Algorithm |
| 3 | O(V^2 * sqrt(E)) hoặc O(V^3) depending on implementation. Rất nhanh trên thực tế, đặc biệt với số lượng cung lớn. | O(V + E) | Push-Relabel (Highest Label Version) |
Bài học kinh nghiệm
- Với đồ thị có n <= 1200 và m <= 120000, Dinic là lựa chọn cân bằng tốt giữa độ phức tạp và khả năng cài đặt.
- Luồng cực đại có thể rất lớn, cần sử dụng
long long(hoặcint64_t) để tránh tràn số. - Các thuật toán Ford-Fulkerson (Edmonds-Karp) thường quá chậm cho các đồ thị lớn trừ khi lưu lượng luồng nhỏ.
Lỗi thường gặp
- Quên trừ dung lượng cung ngược khi dùng ma trận kề hoặc danh sách kề.
- Sử dụng
intcho dung lượng/thông số đầu vào (cầnlong long). - Không tối ưu hóa bộ nhớ (ví dụ: dùng ma trận kề cho đồ thị thưa dẫn đến MLE hoặc TLE do truy cập cache kém).
Bình luận