Flows with Negative Values?
The maximum flow calculated using only positive flow values on each edge can indeed be smaller than the maximum if flow can also be negative. You can easily see why in a trivial graph with only two nodes and two edges:

  ---- capacity 1 ---&gt;
A                      B
  &lt;--- capacity 1 ----


If A is the source node and B is the sink, you can obviously see that if only positive flows are allowed, you get a max flow of 1 but if negative flows are allowed you'd get 2 (with the bottom edge flowing "backwards").

As I commented, the way to figure out the capacity of a graph that allows negative flows as well as positive ones is to restate the problem. Instead of allowing negative flows, add an additional reversed edge everywhere there's a normal edge in the original graph. Then solve the problem with only positive flows. In the trivial example above, you'd have two edges running each direction, and when you found the maximum using only positive flows, you'd get the right answer, 2.