当前位置: 代码迷 >> 综合 >> 最小费用最大流问题
  详细解决方案

最小费用最大流问题

热度:41   发布时间:2024-01-16 13:34:25.0

最小费用最大流就是在原来求最大流的基础上,假设每条边还有一个单位流量所需要的费用,因为最小费用的出现,原本的平行边变得有意义,并且允许反向增广,基本上就是将原本BFS改为进行一次BellmanFord算法寻找最短路径,只要初始流是该流量下的最小费用可行流,每次增广后的新流都是新流量下的最小费用流。下面POJ2135的题解:

题意:

从起点出发,走到终点再回到起点,每条边都对应一个时间,求所需的最短时间。

要点:

这题乍一看很像最短路径,但其实是一个最小费用最大流,可以等效为从起点到终点两次,这两次走过的边没有交集,所以把每条边对应的容量改为1,这样确保只能走一次,再加入一个超级源和一个超级汇,它们对应的容量为2。

15981228 Seasonal 2135
  相关解决方案