Page 1 of 1
11138 - Nuts and Bolts
Posted: Mon Oct 23, 2006 7:01 am
by Timo
I have stuck to solve this problem
.
Can anybody tell me how to solve this problem ?
Thanks
Timotius Sakti
Posted: Mon Oct 23, 2006 7:06 am
by Timo
sorry I have post wrong title
I am asking for 11138 - Nuts and Bolts
Please forgive me moderator
Posted: Mon Oct 23, 2006 7:08 am
by Naani
Maximum bipartite matching?
Posted: Mon Oct 23, 2006 7:14 am
by helloneo
Timo wrote:sorry I have post wrong title
I am asking for 11138 - Nuts and Bolts
Please forgive me moderator
You can change the title..
I solved it with max flow..
Posted: Mon Oct 23, 2006 7:21 am
by Nemo
I tried MaxFlow (Ford Fulkerson). Got TLE in contest. Is yours Ford Fulkerson? How long does it run?
Posted: Mon Oct 23, 2006 7:36 am
by helloneo
Nemo wrote:I tried MaxFlow (Ford Fulkerson). Got TLE in contest. Is yours Ford Fulkerson? How long does it run?
Yes, it's Ford-Fulkerson and it took 1.105 sec..
I used adj list instead of matrix..
Hope it helps
Posted: Mon Oct 23, 2006 5:24 pm
by Timo
Thanks for help me
I have got AC...
Timotius Sakti
???
Posted: Thu Jan 11, 2007 7:54 pm
by Miguel Angel
I solved it with 1.6 secs, I used bipartite max flow...but how do you solve it with less than one second??
Posted: Fri Jan 12, 2007 9:41 pm
by Jan
I used bipartite matching and got accepted in less than .7 sec. So, it actually depends on your matching technique.
Posted: Mon Apr 30, 2007 12:18 pm
by Tommy Wu
I know that this problem is a Maximum-Bipartite-Matching problem.
But can it be implemented by the Edmonds-Karp's algorithm?
I used Edmonds-Karp's algorithm and got a TLE a few hours ago...
Sorry for my poor English grammar.