11439 - Maximizing the ICPC

[pradhanp]

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

[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?

[baodog]

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

[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

[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