Page **1** of **1**

### MinCost MaxFlow with [Undirected Graph]

Posted: **Thu Oct 20, 2005 7:14 am**

by **hank**

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.

### Re: MinCost MaxFlow with [Undirected Graph]

Posted: **Thu Oct 20, 2005 9:53 am**

by **misof**

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.

Posted: **Thu Oct 20, 2005 10:24 am**

by **hank**

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 )

Posted: **Thu Oct 20, 2005 12:29 pm**

by **misof**

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.