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.
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?
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.
@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.
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
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.