In maximum flow if you have double(antiparallel) edges you just add an intermediate node and break the edge in two with the same capacity. In minimum cost flow you can do the same but break the cost also in half or use div to break in half if not even(if cost is 9 for example you break it in 5 and 4). Is this a correct transformation of the graph so you can then proceed with negative cycle canceling?

To make it a bit more clear. I am searching for a way to handle antiparallel edges and create the residual graph. In minimum cost flow you have costs not just capacities like maximum flow.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.