Hello, I've been trying to solve this problem: http://codeforces.me/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?