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?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 151 |
9 | maroonrk | 151 |
Name |
---|
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".
Sorry, forgot to say I used Hopcroft-Karp.
Strange... Show your code, maybe i can help. Solution with O(N ^ 2.376) exists, but i think Hopcroft-Karp must pass.
Here it is: http://pastebin.com/3RH9u4SN
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).
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.
Dinnic works here, my solution accepted in 4.86 seconds.