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

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

### 11138 - Nuts and Bolts

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
sorry I have post wrong title
I am asking for 11138 - Nuts and Bolts

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

Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:
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
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
New poster
Posts: 16
Joined: Thu Apr 14, 2005 10:40 am
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
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
Thanks for help me
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

### ???

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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:
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.