4
2 3 2 11.
.
2 3 0 10, 4 3 0 19.
.

4
2 0 0 47, 3 17 17 25, 4 0 0 38.
1 17 17 31, 3 0 0 23, 4 0 0 96.
1 0 0 96, 2 0 0 48, 4 17 17 91.
.
=
69
2 0, 3 17, 4 1.
1 18, 3 0, 4 0.
1 0, 2 0, 4 17.
.


8
.
1 0 0 39, 5 13 13 21.
5 0 0 87, 8 41 41 92.
5 38 38 85.
6 41 41 14, 8 10 10 49.
2 10 10 69, 3 41 41 58, 4 0 0 73.
6 3 3 59.
.
=
49
.
1 0, 5 13.
5 0, 8 41.
5 38.
6 40, 8 11.
2 10, 3 41, 4 0.
6 3.
.

Edited by author 16.06.2008 04:40

Why?

Please someone explain sample test case. I don't understand how we can push flow 2 through 1->2 (output shows that) if in the input there is flow capacity 1? In the second line of the input there is
2 1 1 1, 3 1 1 3.
that means there is pipeline between 1 and 2 with max flow 1, but there is already 1 flow, so we can't push anything more or something else...?

Thank you in advance.

First i had WA 20, because of wrong apporach, now WA 26...
Maybe somebody have some test ar now something similar to this testcase.

Btw, I am using dijkstra from source to sink with backegde cost of zero. Or this is also wrong?

In test#6 from station N oil is transported to other station.

Edited by author 18.09.2007 00:48

What is the output for the following test?

4
2 3 3 1.
3 3 3 1, 4 1 0 1.
4 4 4 1.
.

Is minimum sufficient amount of money 0 or 1 ???

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

In the former statement of the problem number of quadruples was not exceed 1000000. Now - not more than 100000. VERY bad fact - I think many people (including me) don't solve this problem due to it...

When problemsetters will stop such an idiotism?

I always get stuck at test nr.4 due to an exceeded memory limit. Can't figure out why, tried to tune all structures and algorithm for low consumption. Is it possible to get a test input file to check this ?

Regards,
Christian

Is it guaranteed that there is station, where incoming flow is less than outgoing flow?

Could I output pairs in any order, or they should be sorted by vertex?

First submit: WA #6, I print information about all pipes.

Second submit: AC,I thought, that, if flow at pipe=0, then we don't print information about it at output.

Rejudge - WA #2 at Second Submit.

Third submit: AC, I print information about all pipes.

I don't understand why my first submit is not AC after rejudge.
Is it true, that ALL submits rejudged?


Edited by author 06.11.2006 23:20

Edited by author 06.11.2006 23:20

And where does the oil come from? Station 1?