11138 - Nuts and Bolts

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

11138 - Nuts and Bolts

Post by Timo »

I have stuck to solve this problem :( .
Can anybody tell me how to solve this problem ?

Thanks

Timotius Sakti
"Life is more beautiful with algorithm"

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo »

sorry I have post wrong title :oops:
I am asking for 11138 - Nuts and Bolts

Please forgive me moderator :D
"Life is more beautiful with algorithm"

Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:

Post by Naani »

Maximum bipartite matching?
Last edited by Naani on Mon Oct 23, 2006 7:16 am, edited 1 time in total.
I am signing an important document!

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

Timo wrote:sorry I have post wrong title :oops:
I am asking for 11138 - Nuts and Bolts

Please forgive me moderator :D
You can change the title..
I solved it with max flow..

Nemo
New poster
Posts: 16
Joined: Thu Apr 14, 2005 10:40 am

Post by Nemo »

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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post 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

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo »

Thanks for help me :D
I have got AC...

Timotius Sakti
"Life is more beautiful with algorithm"

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

???

Post 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?? :-?
:D Miguel & Marina :D

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

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

Tommy Wu
New poster
Posts: 6
Joined: Tue Jan 23, 2007 12:32 pm
Location: Kaousiung,Taiwan
Contact:

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

Post Reply

Return to “Volume 111 (11100-11199)”