NRWP - Editorial

Can anyone illustrate this solution graphically, still finding it difficult to understand this editorial.

Are you familiar with max flow algorithms and max-flow min-cut theorem?

@carre I just read about it. But I still need descriptive comments in the tester’s solution. It’s really daunting to understand code despite running it line by line using debugger. Comments would be helpful. I read max-flow algorith for the first time.

OK. If you accept advice, if you are starting with max flow, you should practice it first, it is an important topic and not so easy. You can start with simple problems of direct implementation of the most widely used maximum flow algorithms: Ford-Fulkerson, Edmonds-Karp and Dinic. You can then move on to the minimum-cut max-flow theorem. Those steps are prerequisites for the solution explained in the editorial.

I don’t think the comments on the tester solution would be any more helpful. That solution is conceptually identical to my solution (setter solution) which is full of comments except for the dinic’s algorithm lines. The details of dinic’s algorithms are out of range of the editorial.

2 Likes

Thanks for the advice. I saw the setter’s solution can you tell me what is the function mf,bfs,dfs for ?

As you can see, they are inside the namespace called “dinic”, they are functions of the dinic’s algorithm employed to find the max flow of the network.

There are several resources to read about dinic’s algorithm and one of them is this. As said before, the explanations of the details of dinic’s algorithm is beyond the scope of this editorial.

okay thanks

Can someone explain me:
What is meaning of “rev” in setters code?
What is this (int)g[t].size() in

edge a{t, (int)g[t].size(), 0, cap};
edge b{s, (int)g[s].size(), 0, cap};

How is it useful in dfs part?
image
Thanks in advance

g[i] is a vector that contains the edges coming out from node i. Supose you have and edge from i to j, let’s call it edge e_{ij}, then you also have a reversed edge from j to i, called e_{ji}, that reversed edge is an element of the vector g[j]. The rev property of edge e_{ij} is the index of the vector g[j] where the back edge e_{ji} is located. That information let you access to the reversed edge from the directed edge.

When you send flow df throw the e_{ij} edge you need to update the flow of the reversed edge by -df and that’s when you use the rev property.

Thanks a lot . I got it. :slight_smile:

@carre I have implemented the dinics algorithm (My own implementation not the standard one but similar). Why does it only pass 10 points? Please help!!
This is my first ever flow problem. I just added two directed edge every where to represent it is undirected. Correct me if Im wrong.
CodeChef: Practical coding for everyone (commented)
If there was a bug it should’t have passed the 10 points.

1 Like

Yes, the problem is in the Dinic’s implementation. I have checked a couple of test cases and it is not giving the correct flow. What I would do is stress your Dinic’s implementation with lots of simple graphs and compare the result with the result obtained with a tested implementation

2 Likes

Thanks for taking a look @carre. I couldn’t debug it but got an AC with the standard implementation which is way better than mine.

2 Likes