Hi, I'm really new to Flow algorithms and I'm starting with maximum flow using the EdmondsKarp, I've implemented this version, for the test example extracted from SPOJ FASTFLOW the following test-case has a max-flow of 5, my code answers 3. what would be wrong ? Thanks
Test-Case:
4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3
int max_flow(int source, int sink) {
int residual[MAXN][MAXN]; memset(residual, 0, sizeof(residual));
while(1) {
int prev[MAXN]; memset(prev, -1, sizeof(prev));
int actual[MAXN]; memset(actual, 0, sizeof(actual));
prev[source] = source;
actual[source] = INF;
queue<int> q; q.push(source);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if(capacity[u][v] - residual[u][v] > 0 && prev[v] == -1) {
prev[v] = u;
actual[v] = min(actual[u], capacity[u][v] - residual[u][v]);
if(v != sink) {
q.push(v);
} else {
while(prev[v] != v) {
u = prev[v];
residual[u][v] += actual[sink];
residual[v][u] -= actual[sink];
v = u;
}
goto end;
}
}
}
}
end:;
if(prev[sink] == -1) {
int sum = 0;
for(int i = 0; i < MAXN; i++) {
sum += residual[source][i];
}
return sum;
}
}
}
Better forget about maximum flow unless your handle becomes violet or orange.
I know that my rank is low, but I'm studying a lot about graph theory, I think flows would be a next path since I'm starting to deal good with searches, shortest-paths, bridges and cut points, but I'm also training in other topics as DP, geometry and greedy ;)
Many green and blue ranked users know flow.
Oh, certainly it helps them a lot while they try to solve something like Div2 B/C/D.
Why are they learn all these flows, treaps, suffix arrays if they cannot solve problems which don't require any knowledge of algorithms?
hello, mr. dalex , learning algorithms is not just for contest or problem solving, its for life and fun. then does it matter whether one person is violet or orange ?
dalex You took birth, started competitive programming and without learning algorithms you directly became orange huh?
Yes. I recently learned maxflow and the implementation of Dinic's algorithm. But I have a problem. I'm trying to solve FASTFLOW in SPOJ and I'm getting TLE with Dinic's algorithm. How to optimize? Here is my implementation — http://codeforces.net/blog/entry/15562
I think your code is correct, the max flow value here is 3. The edge (3, 4) can handle only flow of 3, not 5.
By the way you code is very pretty. (:
Thank you, I'm pretty sure it's correct also, do you know any problem which asks for maximum flow without a too strict time as FASTFLOW ? but I think it's wrong also, since there's a possible flow of 3 in the path 1 — 2 — 3 — 4 and 2 from 1 — 3 — 4.
Oh, i got it: these are undirected edges. So for every edge (u, v, c), you should put also edge (v, u, c).
Maybe you can find some problems on maxflow here on Codeforces, try searching the problems from the archive on maxflow tag or smth. Also I recall, Dinic's algorithm gets accepted on FASTFLOW.
but I'm mounting as an undirected graph, take a look:
That's because there are edges (3, 4, 3) and (4, 3, 3) in input. The code overwrites the previous capacities. Add them up and it'll be cool.
Yes, it was the problem, thank you, I'll look for more flow problems, ;) Thanks.
I have solved these problems in java, time limit is not strict.
Data Flow
Internet Bandwidth
The Problem with the Problem Setter
Sabotage
Your implementation is incorrect.
Taking the line "int maxflow(.." as line 1, in lines 21 and 22, you should be updating the capacity matrix as capacity[u][v] -= actual[sink], capacity[v][u] += actual[sink], also increase residual flow as residual[u][v] += actual[sink]. For finding augmenting path in the residual graph, you will need to check if there exists an edge between u and v in the residual graph. That is, in line 11, you will need to check all vertices that can take a flow from u at any point of time. Therefore it is better to take the graph[] as undirected one, or check for all vertices if capacity[u][v] > 0. Similarly in line 15, actual[v] will be checked for minimum with capacity[u][v] and not capacity[u][v] — residual[u][v].
After reading your comment, I still don't see why the implementation is wrong. The array residual is there to avoid unnecessary changes to array capacity, which can be used somewhere later in the code.
Aren't
capacity[u][v] -= actual[sink]
andresidual[u][v] += actual[sink]
the same?You are right, I think only taking the graph[] as undirected one will do. Sorry for the confusion.
I don't know how Edmonds Karp works , but i know Dinic algorithm and i know that dinic is better that edmonds karp if we are talking about complexities.
Wiki
Nice Implementation of FASTFLOW with Dinic
Maybe this be can help you.
This code fails in the following problem. Same statement, just more strict constraint.
http://vn.spoj.com/problems/FFLOW/
Can't figure out why, any idea? :/