关于上下界有源汇最小费用最大流的正确性
  • 板块学术版
  • 楼主wxr_
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/7/24 11:42
  • 上次更新2025/7/24 14:50:16
查看原帖
关于上下界有源汇最小费用最大流的正确性
783628
wxr_楼主2025/7/24 11:42

如题,费用流的正确性一般被认为基于每次优先取最短路增广。而上下界最小费用最大流中要先跑超级源点到超级汇点的最小费用最大流,得到源点到汇点的最小费用可行流,再加上源点到汇点的最小费用最大流。

最后一次跑费用流相当于在可行流的基础上反悔,那么怎么说明在最小费用可行流的基础上跑最小费用最大流的正确性。

2025/7/24 11:42
加载中...