Discussion @ 1833. Hopes of Rowing @ Timus Online Judge

How to solve it?

Posted by Nikita Glashenko [Samara SAU] 27 Jul 2011 16:14

Give me some hint plz.

Re: How to solve it?

Posted by Nikita Glashenko [Samara SAU] 9 Aug 2011 13:50

Solution here (Russian only):
http://codeforces.ru/blog/entry/1797#comment-34342

Re: How to solve it?

Posted by svr 22 Oct 2011 10:48

I red in some book,
Konig: for bipartite graph (V,E) and any weight function w:E->Z+ maximal weight w(M)
of matching is eqal minimal Sum of y(i) where y:V->Z+ some weightes of nodes such that
y(i)+y(j)>=w(e(i,j)).
So, 1) Make bipartite graph 2)find maximal weight matching using hungarian method

Discussion of Problem 1833. Hopes of Rowing