Page 1 of 1

11439 - Maximizing the ICPC

Posted: Mon Mar 31, 2008 2:17 am
by pradhanp
Any hints on this one? One reduction is to maximum matching, which can be done with Edmonds' blossom algorithm. Is there anything simpler?

Posted: Mon Mar 31, 2008 9:59 am
by baodog
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?

Re: 11439 - Maximizing the ICPC

Posted: Tue Apr 01, 2008 7:25 am
by baodog
Nevermind... Heuristics does not work here... have to use matching.

Re: 11439 - Maximizing the ICPC

Posted: Sat Feb 21, 2009 5:53 am
by f74956227
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 :(

Re: 11439 - Maximizing the ICPC

Posted: Sat Sep 05, 2009 3:45 pm
by seckin
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 :)