Discussion @ 1449. Credit Operations 2 @ Timus Online Judge

How to solve this not through simplex method

Posted by Krayev Alexey (PSU) 27 Jun 2006 18:07

Is it reduced to flow or matching ?

Re: How to solve this not through simplex method

Posted by Sandro (USU) 13 Jul 2006 22:24

Hint: you can find the minimum total amount of all bribes (but not the optimal values of bribes) if you know the solution of problem 1076.

Good luck!

Re: How to solve this not through simplex method

Posted by Krayev Alexey (PSU) 19 Jul 2006 21:06

Thank you, i tried to construct algo using this idea, but the second stage of that algo was wrong. Now i fixed it and got ac.
Thank you!

Re: How to solve this not through simplex method

Posted by Lomir 30 Jun 2007 05:00

It is solvable by simplex algorithm!?
Result must be non-negative integers, and integer resulted simplex is NP-complete problem.

Discussion of Problem 1449. Credit Operations 2