I used Greedy(Hungary Algorithm) and Randomization in my Program and Got ACed.

First Time, ACed at 1.000s;
While Second, Failed because TLE.
Third Time, ACed again at 0.015s!!!
Forth Time to Ninth Time, Either OLE or TLE...
Tenth Time, ACed at 0.564s......

What a 'Strange' Program I've Created!

After you do max_match, when you change the un-matched rows' state, there maybe many orders, but some of them are wrong, and will get OLE, so you can use randomization (I think this method is very good! ^_^). But in this problem, you just change the un-matched rows' state in increasing order, then you will get AC. (At the first time, I used decreasing order, but I got OLE :( ,then I used increasing order and got AC with 0.015s :) ).


I'm sorry my English is so poor... :(

Edited by author 10.05.2005 14:46