### MarioYC's blog

By MarioYC19 months ago, ,

Hi everyone, so I found this problem today, and it seems like a really obvious bipartite matching, but I've been getting TLE in it. Is there some faster way to solve it?

 » 19 months ago, # |   0 O(VE) bipartite matching algorithm obviously gets TLE on dense graph with such limits. I think solution which runs in O(sqrt(v) * E) will pass. For example you can use "Hopcroft–Karp algorithm".
•
 » » 19 months ago, # ^ |   0 Sorry, forgot to say I used Hopcroft-Karp.
•
 » » » 19 months ago, # ^ |   0 Strange... Show your code, maybe i can help. Solution with O(N ^ 2.376) exists, but i think Hopcroft-Karp must pass.
•
 » » » » 19 months ago, # ^ |   0 Here it is: http://pastebin.com/3RH9u4SN
•
 » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 Your algorithm works in O(VE) time and it isn't Hopcroft-Karp. Just try this testcase: 500 500 2 2 2 2 2 ... (500 times)2 2 2 2 2 ... (500 times)Copy this a few times and then add "0 0". Your algorithm will work more then 5 seconds (and will get TLE).
•
 » » » » » » 19 months ago, # ^ |   0 Thanks, I found the mistake, I was using the || operator instead of |= when updating the variable change. With this change it still isn't Hopcroft karp because i'm not taking shortest paths, but that only makes it a bit slower.

 » 19 months ago, # | ← Rev. 2 →   +5 Dinnic works here, my solution accepted in 4.86 seconds.