「OI之路」07其他-1网络流

难点就是构图
也有各种变例
决策类问题的法宝之一(还有贪心等)

有个不错的入门教程

网络流-纳米黑客
PDF

最大流解决方案

Edmond-Karp 理论上界是 $nm^2$ ,但通常可以解决$10^3$ ~ $10^4$ 的规模

EK的缺点主要是,每次只找出一条增广路
Dinic算法试图改进这一点

  1. 通过bfs得出残余网络中的分层图(显然是一个dag)
  2. 通过dfs得出增广路,回溯时更新流量
  3. 理论上界是 $n^2m$ ,但通常可以解决$10^4$ ~ $10^5$ 的规模
    特别地,对于二分图匹配,时间复杂度可以达到$O(m \sqrt n)$

当前弧优化:

当层次确定的时候,反向弧是否使用也是确定的
那么如果一条边流完了,可以在边链表中去除
(有点类似欧拉路径的优化)
因为是层次图,不用担心 dfs 对第一个有效边数组的影响
例题:order

最小割

建议看胡伯涛的论文
非常好的题目:「TJOI2015」线性代数

笔记:割上的净流,会统计负流,但割的容量并不统计
定理:任意一个流,其净流=流的大小

费用流

本质上其实就是把EK中bfs换成能处理边权的spfa
(因为dinic无法处理,所以只有EK的衍生版)
费用流的构图需要注意负/正环

至于zkw费用流……
jzq233jzq
zkw

最大权闭合子图

闭合子图:只进不出的子图,可用于处理依赖关系
很容易贪心地想到,最优情况是所有正权点,但为了闭合要有所割舍

考虑有网络流决策,将点分成选和不选两种,用割的模型,以是否和S连通来标识
则S向所有正权点连边,边权为点权,所有负权点向T连边,边权为点权的绝对值
割后,设选的点集为A,不选为B,根据点权正负细分,如图所示:

如果x依赖y,则选x就要选y,此时从x到y连接一条INF的边,标识不可「选x不选y」
注意一个细节(因为我这菜逼一开始忽略了):
这条边是允许选y不选x的,因为那种情况没有造成连通

此时只要是个合法的割,A一定是一个闭合子图,现在要最大化它
显然割=B1-A0,而A=A1+A0
故A+割=A1+A2=正权和,让割最小化即可

有下界网络流

loj上有板子题,代码可以去上面看,以最新提交为准
还有一道板子题:支线剧情

无源汇可行流:
流量平衡下, $\sum d_i=in_i-out_i=0$
先以下界为初始流,边的容量为mx-mi,然后我们希望得到一个流量平衡的流
$若d>0,st->i=d_i,若d<0, i->ed=-d_i$
这个还是比较显然的,就是给每个点一些配额去把多的流量流出去

有源汇(要把去源的、到汇的边去掉):
可行流:
ed->st=INF,于是就是无源汇的了
然后流量就是st->ed那条边此时的可用容量(假装流掉的真实流大小)
这个思想有个不错的题目,「cf708d」Incorrect Flow
最大流:
用可行流的方式构造新图,然后新图上的满流就是原图的可行流,在此之上的操作都能保证其依然是可行流
那么在这个残余网络上,再重新跑一个最大流(ans要清空,然后可行流大小会被st->ed统计到)
费用流:
这里指的是不保证流最大,而是合法流的最小、大费用
做法没什么区别

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/5c7c.html
转载请注明出处,谢谢!