Bài toán
Tìm luồng min cost trên mạng.
Độ phức tạp
có thể lớn hơn O(n.m.m)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> ii;
#define X first
#define Y second
bool minimize(int &a, int b) {
if (a > b)
a = b;
else
return false;
return true;
}
// Network container
int n, m;
vector<ii> a[12309]; //
int c[123][123]; //
int f[123][123]; //
ii d[12309];
bool inqueue[12309];
bool fb(int start, int target) {
queue<int> qu;
for (int i = 1; i <= n; i++) {
inqueue[i] = false;
d[i].X = 1000111000;
}
qu.push(start);
inqueue[start] = true;
d[start].X = 0;
while (qu.size()) {
int u = qu.front();
qu.pop();
inqueue[u] = false;
for (int i = 0; i < a[u].size(); ++i) {
int v = a[u][i].Y;
if (c[u][v] > f[u][v])
if (minimize(d[v].X, d[u].X + (f[u][v] >= 0 ? a[u][i].X : -a[u][i].X))) {
d[v].Y = u;
if (!inqueue[v]) {
qu.push(v);
inqueue[v] = true;
}
}
}
}
if (d[target].X < 1000111000)
return true;
else
return false;
}
int enlarge(int start, int target, int delta, int &answer) {
int i;
for (i = target; i != start; i = d[i].Y)
if (f[d[i].Y][i] < 0)
minimize(delta, -f[d[i].Y][i]);
else
minimize(delta, c[d[i].Y][i] - f[d[i].Y][i]);
for (i = target; i != start; i = d[i].Y) {
f[d[i].Y][i] += delta;
f[i][d[i].Y] -= delta;
}
answer += delta * d[target].X;
return delta;
}
main() {
freopen("input", "r", stdin);
while (scanf("%d%d", &n, &m) > 0) {
for (int i = 1; i <= n; i++)
a[i].clear();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] = c[i][j] = 0;
for (int i = 1; i <= m; i++) {
int p, q, w;
scanf("%d%d%d", &p, &q, &w);
a[p].push_back(ii(w, q));
a[q].push_back(ii(w, p));
c[p][q] += 1;
c[q][p] += 1;
}
int capacity, p;
scanf("%d%d", &capacity, &p);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
c[i][j] *= p;
int r = 0;
while (fb(1, n))
if (capacity == 0)
break;
else
capacity -= enlarge(1, n, capacity, r);
if (capacity != 0)
printf("Impossible.\n");
else
printf("%d\n", r);
}
}
Nhận xét
Code này đã được dùng để nộp cho một bài tập trên UVa. (sau một số chỉnh sửa nhó)
Đề gốc được lấy từ trên UVa.
"Có một mạng dây cáp dùng để vận chuyển tín hiệu. Tất cả các dây dẫn chỉ tải được tối đa K đơn vị tín hiệu (Không có K đon vị tín hiệu nào cùng đi qua một dây dẫn). Cần vận chuyển D đơn vị tín hiệu từ điểm 1 đến điểm n. Với mỗi đơn vị tín hiệu, ta chọn một đường đi từ 1 đến n và di chuyển tín hiệu theo đường đi đó. Để đưa một đơn vị tín hiệu qua một đoạn dây nối từ i đến j (đường nối hai chiều), thì phải mất c[i][j] đơn vị thời gian. Tim cách để vận chuyển D đơn vị tín hiệu với thời gian ngắn nhất. Với ví dụ sau đây, ta cần vận chuyển 20 đơn vị tín hiệu, đầu tiên ta cho một tín hiệu đi theo đường AD, mất 1 thời gian, còn lại 19 đơn vị tín hiệu, làm tương tự với 9 đơn vị tín hiệu nữa. Vậy là ta đã vận chuyển đưuọc 10 đơn vị tín hiệu. Đến đây thì dây nỗi AD đã vận chuyển đủ 10 tín hiệu (Link capacity) thê nên không thể dùng dây nối AD đưuọc nữa. Đối với 10 tín hiệu còn lại, ta chuyển qua đưuọc ABD, mỗi tín hiệu mất 7 thời gian, tổng là ta mất 10+70=80 đơn vị thời gian. (dịch từ UVa)."
(ảnh : UVa)
Để tìm đường tăng luồng cho bài này, mình dùng Ford - Bellman để tìm đường đi có chi phí nhỏ nhất (coi trọng số là 1, nếu gặp cung ngược thì coi trọng số là -1). Vì đề bài yêu cầu chỉ cho D đơn vị luồng chảy vào trong luồng thế nên mình luu capacity là số lượng đơn vị luồng chưa chảy vào trong luồng.
Các lỗi thường gặp
Wrong answer
- Nếu gặp cung ngược thì khi tăng luồng, các bạn phải đảm bảo cung ngược đó chỉ được đưa lên bằng 0.
if (f[d[i].Y][i] < 0) minimize(delta, - f[d[i].Y][i]);
- Kiểm tra giới hạn của kết quả.
Tham khảo
http://pastebin.com/pUVp1365
http://uva.onlinejudge.org/external/105/10594.html