流网络可以看成是一张有向图,只不过这里叫流网络,“容量”即为边权(记 $u,v$ 的容量为 $c(u, v)$),起点 $s$ 就是源点,终点 $t$ 就是汇点。
我们把流网络($G$)表示成一个集合,$G={V, E}$,(其中 $V$ 为点集,$E$ 为边集),其中,如果两个点之间没有边,那么 $c(u, v) = 0$。
我们把 $u,v$ 两点之间的流量记为 $f(u, v)$。
可行流(只需满足以下两个条件):1、容量限制($0 <= f(u, v) <= c(u, v)$) 2、流量守恒(流出流量=流入流量)
一个可行流的流量 $|f|$ = 流出流量-流入流量(一般没有后一项,因一般都不考虑),最大流即为“最大可行流”。
残留网络是对于流网络的某一条可行流来说的,不一样的可行流有不一样的残留网络(残留网络和可行流一一对应)。
残留网络的点集=原网络的点集,边集=所有的边+所有的反向边(后面会解释),我们把残留网络定义为 $c’(u, v)$。
$c’(u, v)$ 有两种情况,如果 $(u, v)\in E $c,那么 $c’(u, v)=c(u, v)-f(u, v)$ ,如果 $(v, u)\in E$那,么 $c’(u, v)=f(v, u)$。(后者即为反向边)
y总在这里形象的说:正向边相当于我们最多(可以在这条边上)加多少,反向边相当于我们最多(可以在这条边上)减多少。
所以,其实反向边我概念其实实在残留网络中才引用出来的,如果流网络原图就用反向边的话,那就会很复杂。
假设原网络可行流为 $f$,残留网络的可行流为 $f’$,那么我们可以得到一些 $f$ 与 $f’$ 的关系。
可以得到 $f+f’$ 也是 $G$ 的一个可行流,且 $|f + f’| = |f| + |f’|$,这里我们定义两个可行流的相加定义为:如果残留网络中的边的方向和原网络相等,那么加上 $f(u, v)$,否则加上 $-f(u, v)$
1、容量限制
因为 $c’(u, v)$ 在正边的情况下,$c’(u,v) = c(u,v) - f(u,v)$ ,所以 $0 <= f’(u, v) <= c(u, v) = c(u, v) - f(u, v)$,移项得到 $0 <= f(u, v) + f’(u, v) <= c(u, v)$,所以满足容量限制。
因为 $c’(u, v)$ 在反边的情况下,$c’(u,v) = f(v,u)$,所以 $0<=f’(u, v)<= c’(u, v) = f(v, u) <= c(v, u)$,移项得到 $c(v, u) >= f(v, u) - f’(u, v) >= 0$,所以满足容量限制。
2、流量守恒
很简单,因为 $f’$ 和 $f$ 都流量守恒,所以加起来也一定流量守恒。
如果在残留网络里面,可以从源点开始,沿着容量大于 $0$ 的边走,一直走到汇点的一条路径即为增广路径。
流网络($G={V, E}$)的割是指把点集 $V$ 分为两个子集 $S,T$(满足 $S∪T = V, S ∩ T = ∅$),满足 s$ ∈ S,t ∈ T$,把这样子集划分的结果就称为 $G$ 的割。
所有的 $S$ 指向 $T$ 的边(横跨集合)的容量之和即为“割的容量”(从 $T$ 指向 $S$ 的边不算),这里区分一下,“最大流”是最大流量,“最小割”是最小容量(用 $c(S, T)$ 表示)。
从 $S$ 流向 $T$ 的流量和 - $T$ 流向 $S$ 的流量和,即为割的流量。(用 $f(S, T)$ 表示)。
对于任意的 $[S, T]$,任意的可行流,$f(S, T) <= c(S, T)$,因为 $T$ 流向 $S$ 的流量和一定是 $>=0$ 的,所以 $S$ 流向 $T$ 的流量 $>= f(S, T)$,因为 $f(u, v) <= c(u, v)$, 所以 $S$ 流向 $T$ 的流量 $<= c(S, T)$,所以 $f(S, T) <= c(S, T)$。
我们看几个性质:1、$f(x, y) = -f(y, x)$, 2、$f(x, x) = 0$, 3、$f(z, x ∪ y) = f(z, x) + f(x, y)$(前提有 $x ∩ y = ∅$),4、$f(z, x) + f(x, y) = f(z, x ∪ y)$$(前提有 x$ ∩ y = ∅)(很显然,就不证了)。
通过这几个性质可以证明:$f(S, T) = |f|$(太难了,我没看懂,自己去看y总视频),所以我们得到 $|f| = f(S, T) <= c(S, T)$,$|f| <= c(S, T)$。
这几个条件相互等价(可以互相推):1、f 是最大流 2、Gf 中一定不存在增广路 3、存在一个割$[S, T] |f| = c(S, T)$。(自己去看y总视频,这里不好写)
$EK$ 算法的模板大约如下(好像是挺简单的(bushi ):
while()
{
1.找增广路。($BFS$,找不到就退出,找得到就找出来)
2.更新残留网络。(直接更新即可)
}
好用心woc
谢鸡哥夸奖/bx/xyx/bx/bx/bx/bx
stO