关于消圈算法的正确姿势

2022/1/6 22:04:05

编程Tag： 算法流量最小最大平衡姿势费用扩广消圈

本文主要是介绍关于消圈算法的正确姿势，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

众所周知当有负环时是跑不出最短路的 233

扩广一下定义，考虑一个不流经 s, t 的负环也能产生贡献

考虑贪心得把所有负边流满，再加反向正边用于退流

首先花最小代价将流量平衡

再从 s 到 t 跑一遍最大流最小费用

输出两次所用费用之和

简单 yy 一下正确性

首先转化后全为正权

这个时候跑流平衡跑出来的全都是 不得不花费 的

在其残余网络上跑最大流最小费用

调整到最大流状态

注意 s,t 无流量限制，应加上 t 到 s 的 inf 边。

这篇关于关于消圈算法的正确姿势的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！