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 1449. Credit Operations 2

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.