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
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 :)
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.