最小费用最大流的负圈问题

前提:初始残余网络,所有正向边cost非负,capacity非负,反向边cost为正向边的相反数,capacity为0。

问题:不停沿着当前残余网络的最短路径增广,残余网络上会出现capacity大于0的反向边,但有可能会出现负圈吗

  • 网上有人提到,每一次增广后的结果,一定是当前流量值下的最小费用流,等价于不存在负圈。

  • 存在负圈→不是最小费用流:如果当前网络流存在负圈,那么可以沿着这个负圈增流该负圈可以承载的最大值,最后不会改变整个网络流的流量(因为这是一个圈,每个节点的流入量都等于流出量,对流量的贡献为0),但是可以消去这个负圈(因为最小容量的那一条边会被充满,变为0)。

  • 反之,不会证

  • 每一次沿着最短路径增广后,新的网络流,一定是当前流量值下的最小费用流,不会证

(虽然感觉是有可能存在负圈,但是由于每次增广都沿着最短路径,新出现的反向边的费用肯定不会太大,和capacity依然大于0的正向边的代数和,真的有可能小于0吗?)

  • 关于该问题,我找了一篇非常好的博客,你可以看看是否有帮助,链接:最小费用最大流