Can’t you explain please this part of Author’s solution
for(i = 2; i < n; i++) {
lift(i);//<-
If I am not mistaken you must lift if the excess is positive but here you don’t know whether the excess is positive or not. And you will not find such k for which
if (fc[k][a[k][i]] > 0 && h[a[k][i]] + 1 < h[k]) h[k] = h[a[k][i]] + 1;
and h[k] = n + n; will stay n+n and later you will not be able to push flow to vertex k.
Where am I wrong ?
Thanks!
If the vertex p lies on the path (s, t) then lca(t, p) should be t and lca(s, p) should be s. If p does not lie on the path, then both the conditions can not be true simultaneously.
This doesn’t make any sense for me. Consider the following tree, with each line containing “node_id: parent(node_id)”:
1: - // root
2: 1
3: 2
4: 1
If s=4, t= 3, we have the following path: 3->2->1->4. Assuming we’d like to test if node 2 is in this path, we now have the following: s=4, t=3 and p=2. So, we have:
- lca(s,p) = 1 != s
- lca(t,p) = 2 != t
Both are different from s and t, so your explanation tells us that node 2 isn’t in the path between 4 and 3, which obviously isn’t true.
2 Likes
Editorial says that Dinic’s algo O(EV^2) can fail … In fact it should fail since, V = 700+700 = 1400 .
But Most of the AC solutions are implemented with Dinic’s algo …
I tried submitting my solution using simple Edmonds-Karp and got AC in 8:33 secs…!!
Does this mean that the test cases were weak…? Or Edmonds-Karp usually does well enough in practice despite it’s worst case runtime complexity of O(VE^2)…?
EDIT: I agree to kevinsogo’s comment. It’s pretty difficult to design strict max-flow cases for a bipartite graph. Especially for this particular problem where we get the B.P.Graph after finding intersections of path’s in a tree. That’s probably the reason Dinitz and even Edmonds-Karp algo was able to find maximum flow within the given time limit for this problem!
3 Likes
When I first read the problem I thought that maybe there is a more specific algorithm for finding the maximum weighted independent set in the bipartite graph, given that the bipartite graph is not arbitrary - it is the intersection graph of two sets of paths in a tree.
For instance, the following problem has a much better solution. If you have a single set of paths in the tree and you generate the graph of their intersections, you can find the maximum weight independent set of this graph in polynomial time (whereas you cannot find it in polynomial time in a general graph). Such graphs are called chordal graphs.
Thus, the graph from the problem is a kind of chordal bipartite graph, so I thought that maybe there is some special algorithm for it which is more efficient than using max-flow. I thought about it and I couldn’t find one, but it would have been nice if one existed.
4 Likes
I implemented Ford-Fulkerson with a mix of BFS (Edmonds-Karp) and DFS augmentation. I do DFS on the first (M1+M2)/2 augmentations, and BFS afterwards. Also, I try a different order of nodes to visit per augmentation, so I expect to usually get short augmenting paths.
This got accepted. I know this shouldn’t pass the time limit, but I guess it’s really hard to generate max flow cases to break such solutions, especially if our graph is bipartite with a specific structure (as mugurelionut explains).
The submission: http://www.codechef.com/viewplaintext/4097453
1 Like
I,too, don’t understand the following part
“If the vertex p lies on the path (s, t) then lca(t, p) should be t and lca(s, p) should be s. If p does not lie on the path, then both the conditions can not be true simultaneously.”.
For, if we choose p=lca(s,t) then the above formula gives “lca(t,p) = p = t = s = lca(s,p”
I don’t think there’s any point to making data that needs faster flow algorithms than Ford-Fulkerson. They’re so rarely required in competitions where you can’t use pre-written code that there’s no point in trying to implement them, it’s simpler to just use a code from somewhere else and source it.
4 Likes
Just a little note on the cross function implemented in author’s solutions: most of the conditionals are useless there. If a path intersects the other, you can test just if lca 1 is between (s1,t1) or if lca 2 is between (s2,t2).
The simplified version of the cross function is as follows:
bool cross (int x1, int y1, int l1, int x2, int y2, int l2){
if(anc(l1, l2) && anc(l2, x1)) return true;
if(anc(l1, l2) && anc(l2, y1)) return true;
if(anc(l2, l1) && anc(l1, x2)) return true;
if(anc(l2, l1) && anc(l1, y2)) return true;
return false;
}
same here 
The tag “min-cost-flow” is wrong. It should be max flow.
pictures are missing. please fix it.
The idea of using DFS augmentation for finding first V/2 augmented path and then using BFS augmentation is really nice!
i can’t see the images
corrected, earlier the constraint was 300 which was later changed to 700. Thank you for informing !!
Hi, yes, you are right. Extremely sorry for writing it wrong.
I have changed the part in the editorial. I had covered only 1 case. May be image might have made it clear. I will upload the image in a while. Thank you for informing.
1 Like
My dinic’s implementation failed, some people got accepted with dinic too. So I think same as kevinsogo.
@1smll: the tag is corrected now. Thanks for point iit out.