11439 - Maximizing the ICPC

All about problems in Volume 114. 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
pradhanp
New poster
Posts: 10
Joined: Mon Mar 31, 2008 2:14 am

11439 - Maximizing the ICPC

Post by pradhanp » Mon Mar 31, 2008 2:17 am

Any hints on this one? One reduction is to maximum matching, which can be done with Edmonds' blossom algorithm. Is there anything simpler?

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Mon Mar 31, 2008 9:59 am

Since time limit is 10 seconds, maybe some sort of heuristic
search works here as well. btw, anyone have a pointer to
a clean, easy to understand, C++ version of the blossom algorithm
on adjacency lists for weighted graphs?

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11439 - Maximizing the ICPC

Post by baodog » Tue Apr 01, 2008 7:25 am

Nevermind... Heuristics does not work here... have to use matching.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: 11439 - Maximizing the ICPC

Post by f74956227 » Sat Feb 21, 2009 5:53 am

How to reduce the problem into a edmon blossom? this graph has weight... i think it is a minimum weight perfect matching in a complete graph..
Am i wrong ?? or could somone give me a hint :(
electron

seckin
New poster
Posts: 3
Joined: Sat Jan 31, 2009 5:43 pm

Re: 11439 - Maximizing the ICPC

Post by seckin » Sat Sep 05, 2009 3:45 pm

you can do that with a binary search on the minimum edge weight combined with maximum matching in an arbitrary graph

can anyone provide us that arbitrary graph matching code?
I would accept PM too :)

Post Reply

Return to “Volume 114 (11400-11499)”