Min Cost Max Flow 0-1 Version

Правка en1, от scopeInfinity, 2017-03-26 13:31:22

For a general Min Cost Max Flow problem cost C associated to an edge having flow F results in C*F .

Thus Objective is to minimize Sigma Ci * Fi, where Fi <= Capacity of ith Edge and giving maximum flow.

0-1 Version

If we have a variation that with a flow F <= Capacity is flowing through an edge only Ci cost should be considered NOT Ci*Fi.

i.e. If edge allows flows its going to cost C or else its going to cost 0.

I am not sure, How can I proceed for it. The optimal cost flow is not required.

Теги max flow, min cost flow, #graph, discrete

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский scopeInfinity 2017-03-26 13:31:22 597 Initial revision (published)