OJ Board

Hello, everybody

I know the method to find the minimum cost maximum flow in a directed grapth.

But how to find
MinCost MaxFlow with an "Undirected" Graph ?

I also see the online judge problem "10594 DataFlow"
the graph in that problem also is undirected.

( I need a simple algorithm , not too difficult. )




Thanks in advance.

hank wrote:Hello, everybody

I know the method to find the minimum cost maximum flow in a directed grapth.

But how to find
MinCost MaxFlow with an "Undirected" Graph ?

I also see the online judge problem "10594 DataFlow"
the graph in that problem also is undirected.

( I need a simple algorithm , not too difficult. )




Thanks in advance.

Simply replace each undirected edge by a pair of directed edges, each of them having the same capacity and length/cost.

Hi, misof

Thanks for your help.

But are you sure the method is correct ?

your method seems to be right only in MaxFlow problem , not in MaxFlowMinCost problem.

( I am not sure ... maybe I am wrong )

Well, for positive edge lengths/costs it should work. Consider a pair of twin edges (an edge from A to B and an edge from B to A). Clearly if there is a positive flow on both of them we can cancel a part of it. This doesn't alter the size of the flow and it lowers its cost. Therefore in an optimal solution at most one of these edges has a positive flow, which exactly corresponds to the undirected case.