Đã có bài viết tìm lát cắt hẹp nhất. edmondskarp.cpp (2)
Đã có bài viết cho luồng có nhiều điểm thu và phát, luồng có giới hạn lưu lượng của nút. edmondskarp.cpp (3)
Đã có bài viết cho luồng min cost (luồng cực đại với chi phí cực tiểu). edmondskarp.cpp (4)
Bài toán
Thuật toán Edmonds-Karp tìm luồng cực đại trên mạng.
Độ phức tạp
tối đa lên đến : O(n.m.m)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <queue>
using namespace std;
#define long long long
void minimize(int &a, int b) {
if (a > b)
a = b;
}
int n, m, source, target;
vector<int> a[12309];
int c[2309][2309];
int f[2309][2309];
int d[12309];
bool findpath(int start, int target) {
queue<int> qu;
for (int i = 1; i <= n; i++)
d[i] = 0;
d[start] = 1000111000;
qu.push(start);
while (qu.size()) {
int u = qu.front();
qu.pop();
//printf("u=%d\n", u);
if (u == target)
return true;
for (int v : a[u])
if (d[v] == 0 && c[u][v] > f[u][v]) {
d[v] = u;
qu.push(v);
}
}
return false;
}
void enlarge() {
int u, v, delta = 1000111000;
for (v = target; (u = d[v]) != 1000111000; v = u)
minimize(delta, c[u][v] - f[u][v]);
for (v = target; v != source; v = u) {
u = d[v];
f[u][v] += delta;
f[v][u] -= delta;
}
}
long answer(int u) {
long r = 0;
for (int v : a[u])
r += f[u][v];
return r;
}
main() {
scanf("%d%d%d%d", &n, &m, &source, &target);
for (int i = 1; i <= m; i++) {
int p, q, w;
scanf("%d%d%d", &p, &q, &w);
a[p].push_back(q);
a[q].push_back(p);
c[p][q] = w;
}
while (findpath(source, target))
enlarge();
printf("%lld\n", answer(source));
}
Nhận xét
Code này đã được dùng để nộp cho một bài tập trên SPOJ.
Các lỗi thường gặp
Runtime error
- Kiểm tra sau lệnh u=qu.front(), có lệnh qu.pop() hay chưa
- Kiểm tra kích thước mảng f và c,
Wrong answer
- Đối với luồng có đường đi hai chiều, để thêm cạnh (p, q) với trọng số w, ta phải viết
a[p].push_back(q);
a[q].push_back(p);
c[p][q]=c[q][p]=w;
- Đối với luồng có đường đi một chiều, để thêm cạnh (p, q) với trọng số w, ta phải viết
a[p].push_back(q);
a[q].push_back(p); // chú ý phải có lệnh này
c[p][q]=w;
- Kiểm tra độ lớn luồng cực đại có vượt quá giới hạn kiểu int không.
- Điều kiện để từ đỉnh u, thăm đến được đỉnh v là if (d[v]==0 && c[u][v] > f[u][v])
- Hai lệnh nầy phải đi cùng nhau
f[u][v] += delta;
f[v][u] -= delta;
- Đối với bài toán luồng có giới hạn dung lượng (lưu lượng) của nút, không được phép làm như sau
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
c[i][j] = min(c[i][j], capacity[i], capacity[j])
code này sẽ sai với nhiều input, ví dụ
4
41 73 2 81
4
1 3 64
2 1 78
2 3 60
1 4 85
2 2
1 2 3 4
(theo acm.uva.es)
theo Ford-Fulkerson, mỗi khi tìm được đường tăng, ta trừ đi khả năng thông qua của mỗi cạnh trên đường đi một lượng delta. Theo như cách này thì trong code của chúng ta, khả năng thông qua của các nút trên được tăng không bị trừ đi. Trong khi đáng ra nó phải bị trừ.