Hướng dẫn giải của Luồng cực đạ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.
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 đích t trong một đồ thị có hướng có trọng số. Luồng cực đại là lượng luồng tối đa có thể đẩy từ s đến t sao cho lượng luồng đi vào một đỉnh (trừ nguồn) bằng lượng luồng đi ra khỏi đỉnh đó (định nghĩa bảo toàn luồng), và lượng luồng trên mỗi cạnh không vượt quá dung lượng của cạnh đó. Bài này có thể áp dụng các thuật toán tìm đường tăng (augmenting path) như Edmonds-Karp (sử dụng BFS) hoặc Dinic (cấp độ). Với ràng buộc n <= 100, m <= 5000 và dung lượng lên tới 2^31-1, cần sử dụng biến kiểu long long để lưu trữ luồng.
Các cách tiếp cận
Cách Edmonds-Karp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const long long INF = 1e18;
long long graph[MAXN][MAXN];
int parent[MAXN];
int n, m, s, t;
bool bfs() {
fill(parent, parent + n + 1, -1);
queue<int> q;
q.push(s);
parent[s] = s;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v = 1; v <= n; v++) {
if (graph[u][v] > 0 && parent[v] == -1) {
parent[v] = u;
if (v == t) return true;
q.push(v);
}
}
}
return false;
}
long long edmondsKarp() {
long long maxflow = 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, graph[u][v]);
}
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
graph[u][v] -= path_flow;
graph[v][u] += path_flow;
}
maxflow += path_flow;
}
return maxflow;
}
int main() {
cin >> n >> m >> s >> t;
for (int i = 0; i < m; i++) {
int u, v; long long c;
cin >> u >> v >> c;
graph[u][v] += c;
}
cout << edmondsKarp() << endl;
return 0;
}
- Time Complexity: O(V * E^2)
- Space Complexity: O(V^2)
Thuật toán Edmonds-Karp sử dụng BFS để tìm đường đi ngắn nhất (tính theo số cạnh) từ s đến t trong đồ thị dư. Mỗi lần tìm được đường đi, ta đẩy luồng bằng dung lượng nhỏ nhất trên đường đi đó (min-capacity) và cập nhật đồ thị dư. Quá trình này lặp lại cho đến khi không còn đường đi tăng cường nào. Với ma trận kề, độ phức tạp là O(V * E^2).
Cách Dinic
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const long long INF = 1e18;
struct Edge {
int to, rev;
long long cap;
};
vector<Edge> adj[MAXN];
int level[MAXN];
int ptr[MAXN];
int n, m, s, t;
void addEdge(int u, int v, long long cap) {
adj[u].push_back({v, (int)adj[v].size(), cap});
adj[v].push_back({u, (int)adj[u].size() - 1, 0});
}
bool bfs() {
fill(level, level + n + 1, -1);
queue<int> q;
q.push(s);
level[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (const auto& e : adj[u]) {
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return level[t] != -1;
}
long long dfs(int u, long long pushed) {
if (pushed == 0 || u == t) return pushed;
for (int& cid = ptr[u]; cid < adj[u].size(); cid++) {
auto& e = adj[u][cid];
int tr = e.to;
if (level[tr] != level[u] + 1 || e.cap == 0) continue;
long long tr_pushed = dfs(tr, min(pushed, e.cap));
if (tr_pushed == 0) continue;
e.cap -= tr_pushed;
adj[tr][e.rev].cap += tr_pushed;
return tr_pushed;
}
return 0;
}
long long dinic() {
long long maxflow = 0;
while (bfs()) {
fill(ptr, ptr + n + 1, 0);
while (long long pushed = dfs(s, INF)) {
maxflow += pushed;
}
}
return maxflow;
}
int main() {
cin >> n >> m >> s >> t;
for (int i = 0; i < m; i++) {
int u, v; long long c;
cin >> u >> v >> c;
addEdge(u, v, c);
}
cout << dinic() << endl;
return 0;
}
- Time Complexity: O(V^2 * E)
- Space Complexity: O(V + E)
Dinic hoạt động theo từng cấp độ. BFS xây dựng cây mức (level graph) chỉ chứa các cạnh từ mức i sang i+1. DFS sau đó tìm và đẩy nhiều luồng cùng lúc trong cây mức đó. Sử dụng mảng ptr để tối ưu hóa, tránh duyệt lại các cạnh đã bão hòa. Thuật toán này hiệu quả hơn Edmonds-Karp, đặc biệt với đồ thị thưa.
Cách Ford-Fulkerson (DFS)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
bool visited[MAXN];
int n, m, s, t;
struct Edge {
int to, rev;
long long cap;
};
vector<Edge> adj[MAXN];
void addEdge(int u, int v, long long cap) {
adj[u].push_back({v, (int)adj[v].size(), cap});
adj[v].push_back({u, (int)adj[u].size() - 1, 0});
}
long long dfs(int u, long long pushed) {
if (u == t) return pushed;
visited[u] = true;
for (auto& e : adj[u]) {
if (!visited[e.to] && e.cap > 0) {
long long tr_pushed = dfs(e.to, min(pushed, e.cap));
if (tr_pushed > 0) {
e.cap -= tr_pushed;
adj[e.to][e.rev].cap += tr_pushed;
return tr_pushed;
}
}
}
return 0;
}
long long maxFlow() {
long long flow = 0;
while (true) {
fill(visited, visited + n + 1, false);
long long pushed = dfs(s, LLONG_MAX);
if (pushed == 0) break;
flow += pushed;
}
return flow;
}
int main() {
cin >> n >> m >> s >> t;
for (int i = 0; i < m; i++) {
int u, v; long long c;
cin >> u >> v >> c;
addEdge(u, v, c);
}
cout << maxFlow() << endl;
return 0;
}
- Time Complexity: O(f * E), với f là luồng cực đại
- Space Complexity: O(V + E)
Đây là cách tiếp cận trực quan nhất. Ta liên tục tìm các đường đi từ s đến t bằng DFS (không quan tâm đến độ dài shortest path) và đẩy luồng qua đường đi đó. Nếu dung lượng các cạnh đều là số nguyên nhỏ, thuật toán này chạy khá nhanh. Tuy nhiên, với dung lượng lớn hoặc các cạnh đặc biệt, độ phức tạp có thể lên tới O(f * E), rất chậm.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(V * E^2) | O(V^2) | Edmonds-Karp |
| 2 | O(V^2 * E) | O(V + E) | Dinic |
| 3 | O(f * E), với f là luồng cực đại | O(V + E) | Ford-Fulkerson (DFS) |
Bài học kinh nghiệm
- Sử dụng đồ thị dư (residual graph) để liên tục tìm các đường đi tăng cường.
- Luồng ngược (reverse edge) là bắt buộc để có thể điều chỉnh luồng khi cần thiết (giải quyết các bước 'lùi lại').
- Dinic nhanh hơn Edmonds-Karp vì nó đẩy nhiều luồng trong một lần xây dựng cây mức (level graph).
Lỗi thường gặp
- Overflow: Cần dùng
long longcho dung lượng và luồng vì c có thể lên tới 2^31-1 và tổng luồng có thể vượt quá giới hạn của int. - Sai sót khi thêm cạnh ngược: Cần đảm bảo chỉ số cạnh ngược (rev) được lưu chính xác để cập nhật dung lượng.
- Quên reset mảng visited/level/parent trong các lần lặp của thuật toán.
Bình luận