11138 - Nuts and Bolts

Timo · Post by **Timo** » Mon Oct 23, 2006 7:01 am

I have stuck to solve this problem

.
Can anybody tell me how to solve this problem ?

Thanks

Timotius Sakti

Timo · Post by **Timo** » Mon Oct 23, 2006 7:06 am

sorry I have post wrong title

I am asking for 11138 - Nuts and Bolts

Please forgive me moderator

Naani · Post by **Naani** » Mon Oct 23, 2006 7:08 am

Maximum bipartite matching?

helloneo · Post by **helloneo** » Mon Oct 23, 2006 7:14 am

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..

Nemo · Post by **Nemo** » Mon Oct 23, 2006 7:21 am

I tried MaxFlow (Ford Fulkerson). Got TLE in contest. Is yours Ford Fulkerson? How long does it run?

helloneo · Post by **helloneo** » Mon Oct 23, 2006 7:36 am

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

Timo · Post by **Timo** » Mon Oct 23, 2006 5:24 pm

Thanks for help me

I have got AC...

Timotius Sakti

Miguel Angel · Post by **Miguel Angel** » Thu Jan 11, 2007 7:54 pm

I solved it with 1.6 secs, I used bipartite max flow...but how do you solve it with less than one second??

Jan · Post by **Jan** » Fri Jan 12, 2007 9:41 pm

I used bipartite matching and got accepted in less than .7 sec. So, it actually depends on your matching technique.

Tommy Wu · Post by **Tommy Wu** » Mon Apr 30, 2007 12:18 pm

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.

OJ Board

11138 - Nuts and Bolts

11138 - Nuts and Bolts

???