Why Deikstra from N-th node to sources backwards get WA20?
Transfer of one indivisible unit of the flow obiously is Deikstra best. What trick may be in test 20?
May be excess of the bound 10000 is forbidden for any money?

AC after year!

Djkstra of course, but in residue net.
Action of "zaem" just is equal to going along residue net.
Beside this the problem actually is not linear, just
piecewise linear. There is classical method of adding additional edge in this situation.
During a long time I could not understand why we may diminish flow along edges but sourses production no.
This becaurse in statement there are not words about
such diminishing but about increasing there are but only in limits from 0 to 1.

Edited by author 30.11.2008 22:06

Dijkstra - you should spell surnames properly

Edited by author 06.01.2007 14:03

I've checked all the numbers in the input - they are correct. But Dijkstra still gets WA #20...

May be, problem in some tricky cases like N = 1? I output "Impossible" in such a case...