Hướng dẫn giải của Luồng cực đại với chi phí nhỏ nhất
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 lưu lượng cực đại từ nguồn (đỉnh 1) đến đích (đỉnh n) trong mạng một hướng, và sau đó tìm chi phí thấp nhất cho lưu lượng đó. Mỗi cạnh có dung lượng (capacity) và chi phí trên mỗi đơn vị lưu lượng (cost). Đây là bài toán Minimum Cost Maximum Flow (MCMF).
Các cách tiếp cận
Cách Min-Cost Max-Flow (SPFA)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct Edge {
int to, rev;
int cap, cost;
};
int n, m;
vector<vector<Edge>> graph;
vector<int> dist, prevv, preve;
void addEdge(int from, int to, int cap, int cost) {
graph[from].push_back({to, (int)graph[to].size(), cap, cost});
graph[to].push_back({from, (int)graph[from].size() - 1, 0, -cost});
}
pair<int, int> minCostMaxFlow(int s, int t) {
int flow = 0, cost = 0;
while (true) {
dist.assign(n + 1, INF);
prevv.assign(n + 1, -1);
preve.assign(n + 1, -1);
dist[s] = 0;
queue<int> q;
vector<bool> in_queue(n + 1, false);
q.push(s);
in_queue[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
in_queue[u] = false;
for (int i = 0; i < graph[u].size(); ++i) {
Edge &e = graph[u][i];
if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
dist[e.to] = dist[u] + e.cost;
prevv[e.to] = u;
preve[e.to] = i;
if (!in_queue[e.to]) {
q.push(e.to);
in_queue[e.to] = true;
}
}
}
}
if (dist[t] == INF) break;
int f = INF;
for (int v = t; v != s; v = prevv[v]) {
f = min(f, graph[prevv[v]][preve[v]].cap);
}
flow += f;
cost += f * dist[t];
for (int v = t; v != s; v = prevv[v]) {
Edge &e = graph[prevv[v]][preve[v]];
e.cap -= f;
graph[v][e.rev].cap += f;
}
}
return {flow, cost};
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
if (!(cin >> n >> m)) return 0;
graph.assign(n + 1, vector<Edge>());
for (int i = 0; i < m; ++i) {
int u, v, c, w;
cin >> u >> v >> c >> w;
addEdge(u, v, c, w);
}
pair<int, int> res = minCostMaxFlow(1, n);
cout << res.first << " " << res.second << endl;
return 0;
}
- Time Complexity: O(V * E * F) (trong thực tế thường nhanh)
- Space Complexity: O(V + E)
Sử dụng thuật toán SPFA (Shortest Path Faster Algorithm) để tìm đường đi ngắn nhất về chi phí giữa nguồn và đích. Lặp lại quá trình tìm đường đi và tăng luồng cho đến khi không còn đường đi khả thi. SPFA có khả năng xử lý cạnh âm tốt.
Cách Min-Cost Max-Flow (Dijkstra with Potentials)
#include <bits/stdc++.h>
using namespace std;
const long long INF_LL = 1e18;
struct Edge {
int to, rev;
int cap;
long long cost;
};
int n, m;
vector<vector<Edge>> graph;
vector<long long> h, dist; // h là potential
vector<int> prevv, preve;
void addEdge(int from, int to, int cap, int cost) {
graph[from].push_back({to, (int)graph[to].size(), cap, (long long)cost});
graph[to].push_back({from, (int)graph[from].size() - 1, 0, -(long long)cost});
}
pair<long long, long long> minCostMaxFlow(int s, int t) {
long long flow = 0, cost = 0;
h.assign(n + 1, 0); // Khởi tạo potential
while (true) {
dist.assign(n + 1, INF_LL);
prevv.assign(n + 1, -1);
preve.assign(n + 1, -1);
dist[s] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (dist[u] < d) continue;
for (int i = 0; i < graph[u].size(); ++i) {
Edge &e = graph[u][i];
if (e.cap > 0) {
long long new_dist = dist[u] + e.cost + h[u] - h[e.to];
if (dist[e.to] > new_dist) {
dist[e.to] = new_dist;
prevv[e.to] = u;
preve[e.to] = i;
pq.push({dist[e.to], e.to});
}
}
}
}
if (dist[t] == INF_LL) break;
for (int i = 1; i <= n; ++i) {
if (dist[i] < INF_LL) h[i] += dist[i];
}
long long f = INF_LL;
for (int v = t; v != s; v = prevv[v]) {
f = min(f, (long long)graph[prevv[v]][preve[v]].cap);
}
flow += f;
cost += f * h[t];
for (int v = t; v != s; v = prevv[v]) {
Edge &e = graph[prevv[v]][preve[v]];
e.cap -= f;
graph[v][e.rev].cap += f;
}
}
return {flow, cost};
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
if (!(cin >> n >> m)) return 0;
graph.assign(n + 1, vector<Edge>());
for (int i = 0; i < m; ++i) {
int u, v, c, w;
cin >> u >> v >> c >> w;
addEdge(u, v, c, w);
}
pair<long long, long long> res = minCostMaxFlow(1, n);
cout << res.first << " " << res.second << endl;
return 0;
}
- Time Complexity: O(F * E log V)
- Space Complexity: O(V + E)
Sử dụng Dijkstra thay vì SPFA để tìm đường đi ngắn nhất. Vì trọng số cạnh có thể âm (do luồng nghịch), ta sử dụng 'potential' (h) để cập nhật trọng số cạnh sao cho chúng luôn dương hoặc không âm, đảm bảo Dijkstra hoạt động đúng. Đây là phương pháp hiệu quả nhất về lý thuyết cho bài toán này.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(V * E * F) (trong thực tế thường nhanh) | O(V + E) | Min-Cost Max-Flow (SPFA) |
| 2 | O(F * E log V) | O(V + E) | Min-Cost Max-Flow (Dijkstra with Potentials) |
Bài học kinh nghiệm
- Bài toán có thể chia làm 2 giai đoạn: tìm lưu lượng cực đại trước rồi tối ưu chi phí, hoặc simultaneous optimization (MCMF). MCMF là cách tiếp cận trực tiếp và hiệu quả.
- Dijkstra không hoạt động với cạnh âm, do đó cần xử lý trọng số bằng cách sử dụng tiềm năng (Potentials) hoặc chấp nhận SPFA nếu đồ thị nhỏ.
Lỗi thường gặp
- Lựa chọn sai thuật toán tìm đường đi (Dijkstra không xử lý được cạnh âm nếu không dùng tiềm năng).
- Sử dụng biến số sai kiểu (int thay vì long long)导致 overflow khi tính chi phí.
Bình luận