Hello, I've been trying to solve this problem: http://codeforces.com/gym/100733/problem/I. I tried to solve it modeling the problem as a flow network. All edges have capacity one. I build the graph twice, one for considering each tree as tree A and the other as tree B. I add M edges from the sink to the highest branches of tree A, and connect the M lowest branches from tree B to the sink. Then I connect all branches that fulfill the inequity abs(Ha — Hb) < T. But, I'm getting wrong answer in test #21. This is my submission: http://ideone.com/6sC2ek.
I would understand a TLE veredict as my solution creates a huge amount of edges about (500^2) in some cases. What would be a better solution for this problem? Is there a way to build this as a flow network and use less edges? I also tried to come up with a DP solution, but I failed to do so. Can anyone point me in the right direction?
This problem is intended to be done with flow. Some gym submissions using dinic got AC under 50ms and even my implementation with Edmond Karp got AC (though it takes about 3s to run).
Is the way I build the graph incorrect then? I don't seem to spot the bug with my code.
I am not finding the bug in your code either — and I also don't know how dinic flow works, so I probably can't be of much help. Also test 21 is really big to debug by hand (we can't even check the whole input)
Stuff to review:
We have vertices capacities, so we have to duplicate a vertex and perform the needed modifications (one part of duplication receive the ingoing edges, the other has the outgoing edges, and we make one edge between them).
I dunno if using dinic you have to rebuild the graph after finding the flow (e.g. after choosing which tree is A and which one is B) — but I did this (I mean, make the residual graph the same as the starting graph)
If I'm not wrong, you are duplicating the edges to avoid parallel edges, correct? Basically you connect the duplicate vertices one to receive incoming edges and the other to send the outgoing flow, correct?
Thanks for your time btw!
I am duplicating the vertices (not the edges) because it's the way you deal with vertex capacity. Let's say we split vertex V into Vin and Vout.
Then the edge between Vin and Vout is equal to the vertex capacity (in the case of the problem it's always equal to one). When another vertex (let's say U, which was also duplicated with Uin and Uout) had an edge to V, we make and edge from Uout to Vin (we also make from Vout to Uin in this case as the edges are not directed).
As far I know, you're doing that to prevent parallel edges. Correct? This shouldn't be a problem with the current Dinic implementation. But thanks for the help.