aviroop123's blog

Negative cycles in MCMF
By aviroop123, history, 6 years ago, In English

Recently I was trying to solve this problem. Somewhere I had seen that the intended solution uses dp with broken profile. But I had a much simpler solution using MCMF. But the problem with this solution is that negative cycles are getting formed. Is there any way to handle negative cycles in MCMF ? I am not familiar with the MCMF algorithm, so it would be better if someone provides the implementation. Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Firstly, you find the flow of value you need (not necessarily maximum one). You can do it with any maxflow algorithm you are comfortable with. Next, you solve the minimum cost circulation problem in the residual graph. To do this you should find negative weight cycles and push flow along them. There is a theorem that the flow f0 is of minimum cost among flows all flows f such that |f0| = |f| if and only if there are no negative cycles.

You can find negative weight cycles with Bellman-Ford

https://cp-algorithms.com/graph/finding-negative-cycle-in-graph.html

You can also add another s - t edge with infinite capacity and minus infinite cost and just run min cost circulation.

And there is actually a page in Russian with this minimum circulation problem.

http://e-maxx.ru/algo/min_cost_flow_negative_cycles

You can also try to search github pages of some red coders. They can occasionally have code libraries there.

→ Reply