1. 网络流
1.1. 定义
1.1.1. 网络
网络是指一个有向图 \(G=(V,E)\),每条边 \((u,v)\in E\) 有一个权值,\(c(u,v)\) 称为容量,当 \((u,v)\notin E\) 时,有 \(c(u,v)=0\)。
特殊地,在图中有源点、汇点两点,分别为 \(s\in V,t\in V\)。
1.1.2. 流
设流函数 \(f(u,v)\to\R(u,v\in V)\) 表示由二元组 \((u,v)\) 向实数集 \(\R\) 的映射,我们称 \(f(u,v)\) 为边 \((u,v)\) 的流量。
流函数 \(f(u,v)\) 需满足以下性质:
- 容量限制:对于每条边,其流量不能超过其容量,即 \(f(u,v)\le c(u,v)\)。
- 斜对称性:相反两边流量和为 \(0\),即 \(f(u,v)=-f(v,u)\)。
- 流守恒性:从源点流出的流量等于流入汇点的流量,也可称除源汇点外所有点流入流出流量相等,即 \(\forall x\in V\land i\notin\{S,T\},\sum f(u,x)=\sum f(x,v)\)。
流函数完整定义:
\[f(u,v)=\begin{cases}f(u,v),&(u,v)\in E\\-f(v,u),&(v,u)\in E\\0,&(u,v)\notin E,(v,u)\notin E\end{cases} \]1.1.3. 其他定义
对于当前状态下的网络,定义源点流出的流量(流入汇点的流量)为网络此状态下(当前流)的流量。
对于边 \((u,v)\) 定义 \(C_f(u,v)\) 为此边容量与流量之差,表示此边的剩余流量,即 \(C_f(u,v)=c(u,v)-f(u,v)\)。
对于图 \(G\) 定义 \(G_f\) 为 \(G\) 中所有节点与剩余流量大于 \(0\) 的边构成的子图,表示残余网络,即 \(G_f=(V,E_f)\),其中 \(E_f=\{(u,v)|c_f(u,v)>0\}\)。
定义增广路 \(P\) 为残余网络 \(G_f\) 上从 \(s\) 到 \(t\) 的路径。
定义割,将点集 \(V\) 分为无交集的两集合 \(A,B\) 且 \(s\in A,t\in B\),这种点的划分方式称为割。定义割的容量为 \(\sum\limits_{u\in A} \sum\limits_{v\in B}c(u,v)\),割的流量为 \(\sum\limits_{u\in A} \sum\limits_{v\in B}f(u,v)\)。若边 \((u,v)\) 中 \(u,v\) 所属点集不同,称此边为一条割边。
1.2. 网络最大流(最小割)
进入正题,给定网络 \(G=(V,E)\) 与源汇,求此网络的最大流量。
1.2.1 最大流最小割定理
最大流等于最小割,证明如下。
对于每一单位的流量,设其经过割边 \((u,v)(u\in A,v\in B)\) 的次数为 \(\mathrm{to}\) 经过边 \((v,u)\) 的次数为 \(\mathrm{back}\)。一定有 \(\mathrm{to}=\mathrm{back}+1\),否则不可能从源点流至汇点。
可以得出流量等于割边流量不大于割边总容量,即割的容量。得出结论:
- 任意一组流的流量不大于一组割的流量。
当最大流存在时,此时残余网络一定无法增广,从而得到 \(s,t\) 不连通,残余网络也不连通,自然我们得到了一组割,此时最大流量等于割的容量。得出结论:
- 存在一组流的流量等于一组割的容量。
综上所述,可以得到最大流等于最小割。
1.2.2. 增广
采用贪心的思想对残余网络 \(G_f\) 进行增广,具体围绕以下两原则:
- 能流满就流满
- 不断寻找增广路
具体地,对于我们在 \(G_f\) 上找到的一条增广路 \(P\),根据能流满就流满的原则,我们令其增加流量 \(c_f(P)=\min\limits_{(u,v)\in P}c_f(u,v)\)。
为保证贪心的正确性,我们尝试加入反悔操作。将边 \((u,v)\) 的流量增加 \(c_f(P)\),可以理解成将边 \((u,v)\) 的剩余容量减少 \(c_f(P)\),我们在进行此操作的同时将反边 \((v,u)\) 的剩余容量减少 \(c_f(P)\),使得我们可以在接下来的操作中进行增广。所以对于每一条边来说我们维护的实际上是其剩余流量。
1.2.3 EK 算法
EK 并不是 EK 鲁比,而是 Edmonds-Karp。
采用 BFS 找一条长度最短增广路,再进行增广,就这样。
时间复杂度为 \(O(nm^2)\),证明详见 OI-Wiki。
1.2.4 Dinic 算法
对于网络用 BFS 进行分层,在 DFS 进行多路增广时只允许向下一层的点转移。这样将网络视为 DAG,规范增广路形态,避免了环的出现。
Dinic 算法的核心优化为当前弧优化。增广时,对于容量等于流量的边无需访问,不是每次遍历都需要从邻接表头进行枚举。我们记录一个第一条没有流满的边,从此进行遍历即可。
优化后的 Dinic 时间复杂度为 \(O(n^2m)\),证明详见 OI-Wiki,我实在是太懒了。
标签:图论,定义,容量,增广,sum,网络,流量,Note From: https://www.cnblogs.com/Eon-Sky/p/17658059.html