无源汇上下界最大流算法的优化
  • 板块灌水区
  • 楼主251Sec
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/3/4 20:49
  • 上次更新2023/10/23 23:04:10
查看原帖
无源汇上下界最大流算法的优化
363415
251Sec楼主2023/3/4 20:49

众所周知,无源汇上下界最大流是一种常用算法,在这个算法中我们通过构造虚拟源点和虚拟汇点来满足流量限制。

我们知道,在完成算法之后,我们需要虚拟源点流出的所有边流满。我们常用的方法是跑完算法之后检查流量。但是我们能不能在算法运行过程中就保证源点出边流满呢?答案是肯定的!

我们发现,如果一条边必须流满,我们就可以把它看作一条下界和上界相等的边。所以,我们只需要解决一个有源汇上下界最大流的问题。众所周知,有源汇上下界最大流可以转化为无源汇求解。所以我们只需要求解这个无源汇最大流问题即可。那么我们可以按照上述流程递归求解,根据 TernaryTree 的结论,可以发现复杂度有所优化!

希望大家能接受这样一个新的算法,希望它能被广泛应用在大家的比赛中!祝大家的 OI 生涯顺利!

2023/3/4 20:49
加载中...