最大流 概念 容量:$capacity(e)$ 表示一条有向边 $e(u, v)$ 的最大允许的流量。 流量:$flow(e)$ 表示一条有向边 $e(u, v)$ 总容量中已被占用的流量。 剩余流量(残量):$w(e) = c(e)-f(e)$,表示当前时刻某条有向边 $e(u, v)$ 总流量中未被占用的部分。 反向边:原图中每一条有向边在残量网络中都有对应的反向边,反向边的容量为 $0$,容量的变化与原边相反;『反向边』的概念是相对的,即一条边的反向边的反向边是它本身。 残量网络:在原图的基础之上,添加每条边对应的反向边,并储存每条边的当前流量。残量网络会在算法进行的过程中被修改。 增广路(augmenting path):残量网络中从源点到汇点的一条路径,增广路上所有边中最小的剩余容量为增广流量。 增广(augmenting):在残量网络中寻找一条增广路,并将增广路上所有边的流量加上增广流量的过程。 层次:$level(u)$ 表示节点 $u$ 在层次图中与源点的距离。 层次图:在原残量网络中按照每个节点的层次来分层,只保留相邻两层的节点的图,满载(即流量等于容量)的边不存在于层次图中。 流的三个重要性质:
容量限制:对于每条边,流经该边的流量不得超过该边的容量,即,$f(u,v)\leq c(u,v)$ 斜对称性:每条边的流量与其相反边的流量之和为 0,即 $f(u,v)=-f(v,u)$ 流守恒性:从源点流出的流量等于汇点流入的流量,即 $\forall x\in V-{s,t},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$ 最大流问题:指定合适的流 $f$,以最大化整个网络的流量(即 $\sum_{(s,v)\in E}f(s,v)$)。
Ford-Fulkerson 增广 增广路指一条从 $s$ 到 $t$ 的路径,路径上每条边残余容量都为正。把残余容量为正($w(u, v) \gt 0$)的边设为可行边,然后搜索寻找增广路。
找到一条增广路后,这条路能够增广的流值由路径上边的最小残留容量 $w(u, v)$(记为 $flow$)决定。将这条路径上每条边的 $w(u, v)$ 减去 $flow$。最后,路径上每条边的反向边残留容量要加上 $flow$。...