boleyn.su's blog

An implementation of Cycle-canceling Algorithm WANTED!
By boleyn.su, 11 years ago, In English

Description

I am working on my template for min cost max flow problems.

However after I implemented the most usually used Successive Shortest Path Algorithm, I found it hard to implement Cycle-canceling Algorithm(I got either a Runtime Error or a Wrong Answer Time Limit Exceeded). As far as I know, Successive Shortest Path Algorithm cannot handle the network with negative cycles, so I think it is important to learn Cycle-canceling Algorithm.

I knew someone solved this problem using Cycle-canceling Algorithm ( btw I can solve it without using Cycle-canceling Algorithm ) , while my implementation failed. I guess there must be some better implementations. So I googled its implementation, but found nothing.

I am asking for your help. Any material about it is great. Thanks!

References

Topcoder>Algorithm Tutorials>Minimum Cost Flow, Part 2: Algorithms

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

»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

http://community.topcoder.com/stat?c=problem_solution&rm=312044&rd=14730&pm=11217&cr=22840511

I used to write one during that SRM , hope that can help you :)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    THX. In fact, I thought about implementing it by a dfs version of SPFA, but I guess it may cause segment fault sometimes, and to handle the stack by myself leads to a lot more codes.

    → Reply