Published on

Maximum flow problem

Maximum flow problems involve finding a feasible flow through a flow network that maximizes the flow rate.
The order of the path from source to sink is not important.
After finding the max flow, draw the residual graph and check if there is room for further improvement.

Residual Network:

c(u, v) is

  • c(u, v) - f(u, v): send the amount about empty room
  • f(v, u): give back the amount I recieved
  • Give back what you received and receive the available amount.