变种网络流总结

发布时间 2023-09-25 11:03:10作者: 灰鲭鲨

最小费用循环流

考虑如果费用全部是正的,那么最小费用一定是0.

可以强制把所有负边流满,留下反悔边。如果一个点出度大于入度,那么这个点向虚拟汇点连出度减入度,否则从虚拟源点向这个点连入度减出度。

无源汇上下界可行流

先强制把下界流满,统计每个点的流出和流入。

如果流出比流入多就从这个点向虚拟汇点连出度减入度,否则从虚拟源点连入度减出度。

然后看一下是否满流,满流的话每条边流量加上其下界就是答案,不满流无解。

有源汇上下界可行流。

设源点为 \(S\),汇点为 \(T\),虚拟源点为 \(S'\),虚拟汇点为 \(T'\)
从汇点向源点连一条 \(\infin\) 的边,跑无源汇上下界可行流。

有源汇上下界最大流

先可行流,设此时 \(T->S\) 的这条边的流量为 \(f_1\),然后去掉这条边,从 \(S\)\(T\) 跑一遍最大流 \(f_2\),此时 \(f_1+f_2\) 为上下界最大流,每条边流量为现在图流量加上流量下界