Fastflow - wa

[justadream]

Hello, I tried to solve this problem https://www.spoj.com/problems/FASTFLOW/ but I’m getting wrong answer. This is my first time learning about maximum flow. I’m using Dinic Algorithm to slove it, but there is something that I don’t understand. In this problem, the graph is undirected but in the article that I’m reading the graph is directed, and there is source and sink, so in this problem I’m assuming the source is node 1 and the sink is node N, correct me if I’m wrong about that.

Here’s my implementation:

EDIT: Code removed. Already accepted, I just need to add negative flow to the reverse edge.

[simes]

What does it mean when DFS returns in, i.e. INF, and should this value be summed into res by the main loop?

[justadream]

What does it mean when DFS returns in, i.e. INF, and should this value be summed into res by the main loop?

in is INF only at the first vertice, and DFS return in only at the last vertice, so the DFS return INF only if first vertice = last vertice i.e. there is only one vertice, which won’t happen since the constrain is 2 <= N <= 5000, N is the number of vertices.

[simes]

out = dfs(adj, edg, lv, y, n, getMin(in, edg[e]));

out is an int, but dfs returns a long long int. Could you be getting overflow?

[justadream]

Already accepted, I just need to add negative flow to the reverse edge.