I_love_tigersugar's blog

Maximum flow of network with minimum capacity
By I_love_tigersugar, 10 years ago, In English

Given a network G=(V,E) with s and t being the source and the sink of G, respectively.

For each edge (u,v), there are two numbers c(u,v) and d(u,v). They represent the minnimum and the maximum amount of flow that can pass through the edge (u,v), respectively. I.e, the flow of edge (u,v) f(u,v) must satisfies: c(u,v)<=f(u,v)<=d(u,v).

How can I find the maximum flow from s to t?

Thanks in advance.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

It can be reduced to max-flow without lower bounds: http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

We compacted it a bit to fit in our ACM Team Contest Reference:

  • feasible flow in a network with both upper and lower capacity constraints, no source or sink: capacities are changed to upper bound — lower bound. Add a new source and a sink. let M[v] = (sum of lower bounds of ingoing edges to v) — (sum of lower bounds of outgoing edges from v). For all v, if M[v]>0 then add edge (S,v) with capacity M, otherwise add (v,T) with capacity -M. If all outgoing edges from S are full, then a feasible flow exists, it is the flow plus the original lower bounds.
  • maximum flow in a network with both upper and lower capacity constraints, with source s and sink t: add edge (t,s) with capacity infinity. Binary search for the lower bound, check whether a feasible exists for a network WITHOUT source or sink (B).
→ Reply