¶ Luồng với chi phí cực tiểu
- Tác giả: Võ Đức Đoàn - THPT Chuyên Nguyễn Tất Thành, Kon Tum
- Reviewer:
- Đặng Đoàn Đức Trung - UT Austin
- Trần Quang Trường - Trường Đại học Công Nghệ Thông tin, ĐHQGHCM
- Nguyễn Đức Kiên - Trường Đại học Công nghệ, ĐHQGHN
¶ Kiến thức cần biết
Trước khi đọc bài viết này, bạn nên đọc và hiểu những kiến thức từ các bài viết:
- Luồng cực đại trên mạng.
- Chuỗi bài viết các thuật toán tìm đường đi ngắn nhất: Phần 1 - Phần 2 - Phần 3.
¶ Luồng với chi phí cực tiểu
Bài toán luồng với chi phí cực tiểu là các bài toán yêu cầu ta phải gửi luồng trên mạng với chi phí nhỏ nhất có thể.
¶ Mạng
Giả sử ta được cho một mạng (network) là một đồ thị có hướng gồm các đỉnh và các cung nối các đỉnh lại với nhau. Mỗi cung trên mạng sẽ có hai trọng số và chỉ lượng luồng có thể đi qua và chi phí khi gửi một đơn vị luồng đi qua cung này.
Số bên trái là sức chứa, số bên phải là chi phí
Nhiệm vụ của ta khi gửi luồng trên mạng, ta cần cực tiểu hóa chi phí gửi luồng từ đỉnh nguồn đến đỉnh thu .
¶ Bài toán
Ta có bài toán sau: Cho một mạng có là số đỉnh và là số cạnh, tìm luồng cực đại trên mạng với chi phí cực tiểu.
Ta sẽ xây dựng thuật toán giải quyết bài toán này dựa theo phương pháp Ford-Fulkerson.
¶ Đồ thị thặng dư
Để xây dựng đồ thị thặng dư cho mạng , ta cần tạo một đồ thị có hướng sao cho:
- Đỉnh: Các đỉnh có trong đều có trong , hay .
- Cạnh xuôi: Với mỗi cung có trong , sẽ tồn tại một cạnh có hướng trong có sức chứa thặng dư bằng và có chi phí bằng .
- Cạnh ngược: Với mỗi cung có trong , sẽ tồn tại một cạnh có hướng trong có sức chứa thặng dư bằng và có chi phí bằng .
Sở dĩ ta cho cạnh ngược có chi phí là bởi cạnh ngược là các cạnh được dùng để hủy luồng đi qua cung trên mạng, và vì luồng đã bị hủy nên ta cũng loại bỏ chi phí khi đi qua cung ấy.
¶ Đường tăng luồng
Các thuật toán áp dụng phương pháp Ford-Fulkerson khi tìm luồng cực đại sẽ thực hiện tăng luồng với mỗi đường tăng luồng trên mạng mà nó tìm được sau mỗi bước.
Để cực tiểu hóa chi phí, ta cần tìm đường tăng luồng có chi phí gửi luồng nhỏ nhất có thể ở mỗi bước để cực tiểu hóa chi phí. Việc tìm những đường tăng luồng này có thể được thực hiện bằng các thuật toán tìm đường đi ngắn nhất xử lí được trường hợp cạnh có trọng số âm như thuật toán SPFA. Ở đây, ta sẽ sử dụng thuật toán Johnson.
¶ Thuật toán
Trước khi nói về phần cài đặt thuật toán, ta sẽ giới thiệu về thuật toán Johnson.
¶ Thuật toán Johnson
Thuật toán Johnson là thuật toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị có hướng. Tuy nhiên, vì bài toán chỉ yêu cầu ta tìm đường tăng luồng với chi phí nhỏ nhất nên thuật toán sẽ được mô tả một cách đơn giản hơn.
Thuật toán bắt đầu bằng việc gán mỗi đỉnh trên mạng một giá trị bằng giá trị của đường đi ngắn nhất từ đỉnh đến đỉnh . Sau đó, ta cập nhật trọng số của các cung trên đồ thị bằng giá trị mới . Ta có thể chứng minh trọng số mới trên các cung sẽ có giá trị không âm bằng bất đẳng thức tam giác (xem ba đỉnh là ba đỉnh của một tam giác với độ dài ba cạnh ).
Sau khi tìm đường đi ngắn nhất từ đến trên đồ thị có các trọng số mới này, ta có thể tìm lại giá trị của đường đi ngắn nhất trên đồ thị gốc bằng cách trừ đi với mỗi cạnh trên đường đi ngắn nhất, hoặc chỉ cần trừ đi . Ta có thể chứng minh được rằng đường đi ngắn nhất từ đến trên đồ thị với các trọng số mới cũng là đường đi ngắn nhất từ đến trên đồ thị gốc.
Chứng minh
Ta có là một đường đi ngắn nhất trên đồ thị có trọng số mới. Giá trị của đường đi trên đồ thị bằng:
Công thức trên tương đương với:
Vì và không phụ thuộc vào nên ta có thể kết luận rằng cũng là đường đi ngắn nhất trên đồ thị gốc.
Về độ phức tạp của thuật toán Johnson: ở bước đầu tiên, vì đồ thị có các trọng số âm nên ta sử dụng thuật toán Bellman-Ford. Ở bước thứ hai, vì giá trị của các trọng số mới không âm, ta sử dụng thuật toán nhanh hơn để giải quyết - thuật toán Dijkstra. Độ phức tạp của Bellman-Ford và Dijkstra lần lượt là và nên độ phức tạp của thuật toán sẽ bằng .
¶ Cài đặt
Khi áp dụng thuật toán Johnson để tìm các đường tăng luồng, bước một chỉ cần thực hiện một lần như một bước tiền xử lí khi mạng có trọng số âm, còn bước hai sẽ thực hiện một hoặc nhiều lần để tìm các đường tăng luồng ấy.
Ta có thể hiểu rõ hơn về cách áp dụng qua chương trình mẫu dưới đây.
struct MinCostFlow{
struct Edge{
int u, v; long long c, w; // c(uv) = c, a(uv) = w
Edge(){}
Edge(int _u, int _v, long long _c, long long _w) : u(_u), v(_v), c(_c), w(_w) {}
};
const long long INF = 1e18;
vector<vector<int>> adj; // danh sách kề
vector<Edge> edge; // danh sách cạnh
vector<long long> pi; // giá trị pi(u) trong thuật toán Johnson
vector<pair<int, int>> p;
vector<bool> vst;
vector<long long> d;
int n; // số lượng đỉnh
int s, t; // đỉnh nguồn - đỉnh thu
bool negCost = 0; // đồ thị có tồn tại cạnh có chi phí âm
MinCostFlow(){}
MinCostFlow(int _n, int _s, int _t):
n(_n), s(_s), t(_t), adj(_n), vst(_n), pi(_n, 0), p(_n), d(_n) {
// các đỉnh được đánh số từ 0 đến n - 1
edge.clear();
}
void addEdge(int u, int v, long long c, long long w, long long bc = 0){
// thêm cạnh
adj[u].emplace_back(edge.size()); edge.emplace_back(Edge(u, v, c, w)); // cạnh xuôi
adj[v].emplace_back(edge.size()); edge.emplace_back(Edge(v, u, bc, -w)); // cạnh ngược
negCost |= (w < 0); // kiểm tra nếu chí phí âm
}
void edgeflow(int id, long long flow){
// flow luồng đi qua cạnh có chỉ số id
edge[id].c -= flow; // cạnh uv
edge[id ^ 1].c += flow; // cạnh vu
}
void bellmanford(){
// thực hiện tiền xử lí khi mạng tồn tại cạnh có chi phí âm
if(!negCost) return;
fill(pi.begin(), pi.end(), INF);
pi[s] = 0;
for(int i = 1; i < n; ++i){
bool upd = 0;
for(Edge &e: edge){
if(pi[e.u] + e.w < pi[e.v]){
pi[e.v] = pi[e.u] + e.w;
upd = 1;
}
}
if(!upd) break;
}
}
pair<long long, long long> dijkstra(){
// tìm đường tăng luồng
fill(vst.begin(), vst.end(), 0);
fill(d.begin(), d.end(), INF);
d[s] = 0;
priority_queue<pair<long long, int>> pq;
pq.push({0, s});
int u, v; long long w, tmp;
while (!pq.empty()) {
tie (tmp, u) = pq.top(); pq.pop();
if(vst[u]) continue;
vst[u] = 1;
for(int id : adj[u]){
v = edge[id].v; w = edge[id].w + pi[u] - pi[v];
if(edge[id].c > 0 && d[u] + w < d[v]){
d[v] = d[u] + w;
p[v] = {u, id};
pq.push({-d[v], v});
}
}
}
for(int i = 0; i < n; ++i) pi[i] = min(pi[i] + d[i], INF); // cập nhật giá trị
if(!vst[t]) return {-1, -1}; // không tìm thấy đường tăng luồng
// tìm thấy đường tăng luồng
// tìm điểm nghẽn và chi phí
long long flow = INF, cost = 0;
int cur = t;
while(cur != s){
flow = min(flow, edge[p[cur].second].c);
cost += edge[p[cur].second].w;
cur = p[cur].first;
}
return {flow, cost};
}
pair<long long, long long> MinCostMaxFlow(){
bellmanford(); // tiền xử lí
long long flow = 0, cost = 0, bottleneck, c;
while((tie(bottleneck, c) = dijkstra(), bottleneck) > 0){ // tìm thấy đường tăng luồng
// tăng luồng
flow += bottleneck;
cost += c * bottleneck;
int cur = t;
while(cur != s){
edgeflow(p[cur].second, bottleneck);
cur = p[cur].first;
}
}
return {flow, cost}; // {luồng cực đại, chi phí cực tiểu}
}
};
Gọi là giá trị của luồng cực đại trên mạng. Vì số lượng đường tăng luồng tối ta có thể tìm được là nên khi sử dụng thuật toán Johnson để tìm đường tăng luồng, độ phức tạp của thuật toán tìm luồng cực đại với chi phí cực tiểu của ta bằng .
Đối với các bài toán yêu cầu ta gửi đúng đơn vị luồng trên mạng, ta có thể thêm một hàm giúp giải quyết dạng bài này vào chương trình trên.
long long sendKFlow(long long k){
bellmanford();
long long cost = 0, bottleneck, c;
while(k > 0 && (tie(bottleneck, c) = dijkstra(), bottleneck) > 0){ // tìm thấy đường tăng luồng
// tăng luồng
bottleneck = min(bottleneck, k);
k -= bottleneck;
cost += c * bottleneck;
int cur = t;
while(cur != s){
edgeflow(p[cur].second, bottleneck);
cur = p[cur].first;
}
}
if(k != 0) return INF; // không thể gửi K luồng trên mạng
return cost; // chi phí cực tiểu
}
Độ phức tạp khi này bằng .