Обсуждение @ 1449. Кредитные операции 2 @ Timus Online Judge

How to solve this not through simplex method

Послано Krayev Alexey (PSU) 27 июн 2006 18:07

Is it reduced to flow or matching ?

Re: How to solve this not through simplex method

Послано Sandro (USU) 13 июл 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

Послано Krayev Alexey (PSU) 19 июл 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

Послано Lomir 30 июн 2007 05:00

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

Обсуждение задачи 1449. Кредитные операции 2