费用流的算法有很多种，Spfa算法的十分好理解，消圈算法是什么呢？
倘若在费用流中存在负权圈怎么办呢?
这时我们就需要用消圈算法，消圈算法怎么理解呢？
就是先跑一次最大流，这时图就变成了一个残余网络。
那么如果S-T存在负权的路径，或者有负环存在，
那么就表示当前的不是最优的，然后不断消除负环，负边来改善残余网络，
当不存在负圈，这时到达最优，即可。
具体看https://www.cnblogs.com/longdouhzt/archive/2012/05/20/2510743.html
本文共 301 字，大约阅读时间需要 1 分钟。
费用流的算法有很多种，Spfa算法的十分好理解，消圈算法是什么呢？
倘若在费用流中存在负权圈怎么办呢?
这时我们就需要用消圈算法，消圈算法怎么理解呢？
就是先跑一次最大流，这时图就变成了一个残余网络。
那么如果S-T存在负权的路径，或者有负环存在，
那么就表示当前的不是最优的，然后不断消除负环，负边来改善残余网络，
当不存在负圈，这时到达最优，即可。
具体看https://www.cnblogs.com/longdouhzt/archive/2012/05/20/2510743.html
转载于:https://www.cnblogs.com/fengzhiyuan/p/7943937.html