ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1833. Hopes of Rowing

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