"Any Flow" Minimum Cost

Revision en1, by LoppA, 2017-05-30 22:53:51

Hi, in this problem from HackerRank we abstract the problem to a directed graph with capacity and cost on the edges, source and sink and we need to get the minimum cost despite the flow (as long as we don't exceed the capacities).

To achieve that, we just need to change the Max Flow Min Cost algorithm breaking it when the best augmenting path we found has total cost greater than zero. Link to editorial: here (he changed the problem to Maximum Cost so he breaks it when the best augmenting path has cost smaller than zero).

My doubt is: Does this algorithm to get Minimum Cost with "Any Flow" work specifically for this problem's class of graph or does it work for every other cost-flow graph?

Tags min cost max flow, flow, #graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English LoppA 2017-05-30 22:53:51 875 Initial revision (published)