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 ???

How can it be equal to 0? I think correct answer is:

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

Well, the problem statement is not clear.
Obviously, nodes 1 and 3 can produce oil, so
technically we can reorganize whole network as follows:

1. Substract one item of flow from 2 to 3, since 3 can produce oil itself and easily can increase it's output by 1
2. Add flow of value 1 from node 2 to 4

Thus, to increase flow by one we need not to increase any
capacities and answer is 0.

Edited by author 12.01.2007 13:05

Hm, I think, you can be right... I'll try to implement it...

Yes, the idea described above is really right...

But this idea means that we must find min cost flow
with value 1 unit greater from 0-flow initial flow
not as additional flow,or make absolute new
flow distribution.
It seems that there is additional difficulty
that cost per- unit is 0 before capacity and c[i] after
capacity, or discontinious.
Thus problem seems non-standard.Don't say us secret,
best celebration to find ourselves.