最大流
一些定义
流网络：\(G=(V,E)\) 一个连通图满足 \(|E|\ge |V|-1\) ，其中有源点 \(S\) 汇点 \(T\)
每一条边 \((u,v)\) 有一个非负容量 \(c(u,v)\ge 0\)
流：边 \((u,v)\) 的流是一个函数 \(f(u,v)\) ， \(\forall u,v\in V\) ，满足
-
\(f(u,v)\le c(u,v)\)
-
\(f(u,v)=-f(v,u)\)
-
流守恒性：若 \(u\notin\{S,T\}\) ，要求 \(\sum_v f(u,v)=\sum_w f(w,u)\)
流进 \(u\) 的总流量=离开 \(u\) 的总流量
网络的流：流 \(f\) 定义为 \(f=\sum_{v\in V} f(S,v)\)
-
即从源点出发的总流表示网络的流。
在最大流问题中，求 \(S\) 到 \(T\) 的最大值流
边的残留容量： \(r(u,v)=c(u,v)-f(u,v)\)
残留网络：流 \(f\) 的残留网络 \(G_f=(V,E_f)\) ，
其中 \(E_f=\{(u,v)\mid u,v\in V\and r(u,v)>0\}\)
-
若 \(0<f(u,v)<c(u,v)\) 则 \((u,v)\) 在残留网络中，且
\(r(v,u)=c(v,u)-f(v,u)>0\) ，所以 \((v,u)\) 也在残留网络中
增广路径：增广路径 \(P\) 是残留网络中 \(S\) 到 \(T\) 的一条简单路径
增广路径的残留容量： \(\delta(P)=\min\{r(u,v)\mid(u,v)\in P\}\)
沿着路径增广 ：沿着路径的每一条边发送 \(\delta(P)\) 的流。
相应地，修改流的值与残留容量
- \(f=f+\delta(P)\)
- \(\forall(u,v)\in P\) ，\(r(u,v)\leftarrow r(u,v)-\delta(P)\) ，\(r(v,u)\leftarrow r(v,u)+\delta(P)\)
FF 算法
伪代码
int FF()
{
f = 0;
创建残留网络 G(f);
while (在G(f)中存在从 s 到 t 的有向路径)
{
令 P 是在G(f)中从 s 到 t 的一条路径
delta = delta(P)
沿着 P 发送 delta 单位的流
更新 P 上的边的残留容量
f = f + delta;
}
return f; //f是最大流
}