本文主要是介绍压入与重标记算法（预流推进算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最大流算法之压入与重标记算法（预流推进算法）
1.算法发现者:
Goldberg && Tarjan( 87 ):
不了解Goldberg，不过对Tarjan有所了解，他还是斐波那契堆，LCA，强连通分量Tarjan算法的发现者，也是算法大师高德纳的弟子。
2.算法动机:
在一个有向图中，寻找从源点( source )到汇点( sink )的最大流( max flow )；
3.算法时间复杂度:
O（V*V*E）；
4.最大流算法的一些名词定义，限制:
A. 流网络( flow network ) :
G = ( V, E ) 的有向图;
B. vertex s : 源点 && vertex t : 汇点;
C. 每条edge( u, v )∈E 有 capacity( u, v ) > 0;
若 ( u, v ) ∉ E 有 capacity( u, v ) = 0;
D. 流量图（flow map）:
edge（u，v）的当前已行流的大小 f（u, v） ≤ capacity（u, v） && f（u, v） = - f（u, v）（反对称）;
E. 饱和边（ saturated edge（u, v） ）:
capacity（u, v） == f（u, v）;
F. edge（u, v）的残余量 residual（u, v):
capacity（u, v） - flow（u, v）;
G. 残余图（ residual graph ） RG( V, E' ):
edge( u, v ) ∈ E' 有 residual（u, v） >= 0;
H. 增广路（ augmenting path ）:
在残余网络RG上一条从 s 到 t 的可达路径；
I. 最大流（max flow）:
无增广路存在；
5.压入与重标记算法引入的新名词的定义:
A. 余流（excess flow）:
依旧储存在该顶点，尚未排出的流量 excess（u） = ∑ f（V，v） >= 0;
B. 活性点（active vertex）v:
v ∈ V - { s, t } && d( v ) < ∞ && excess( v ) > 0，该点流量溢出;
C. 点的高度height（u）:
每个顶点被赋予一个高度，余流只能从高往下压入比他低的顶点;
D. 合法标记（legal labeling）:
edge（u， v） ∈ E，height（u） <= height（v） + 1，算法仅仅将流从u 压入 v 当 height（u） = height（v） + 1;
6.算法抽象思想:
和Edmonds-Karp， Dinic思想算法不同，在残余网络RG中，算法不寻找增广路AP。
算法假设每个顶点u存在无限大容量的水库，可以用来储存任意多的水，
储存在该顶点的流量被称为该点的余流（excess（u）） 。
算法在开始时，使得所有从源点 s 出来的边，达到饱和状态，即saturated edge。
然后努力使得这个前置流( pre flow )达到汇点 t。然而，无法达到t的流量，全部返回给源点 s 。
算法开始时，除了height（s）= |V|，height（t）= 0（固定不变），
其余点都初始化为height（u）= 0（可变）；
每个顶点与它相关联的的顶点处于同一平台，然而需要Push（u）的流量的时候，
需要适当调整height（u）（即重标记relabel（u）），才可以使得excess（u），流向高度小于它的顶点v。
但是高度较低的顶点到高度较高的顶点可能存在一条正向网络流，但是“对流”的处理，都是往下的。
需要注意的是，调整height（u）时，需要增加到比其最低的相邻顶点 v 的高度高一个单位，
也就是height（u） = height（v） + 1；
下面解释算法的具体操作。
7.算法流量限制:
A. ∀（u，v）∈ V => f（u, v）<= capacity（u, v）（容量限制）
B. ∀（u，v）∈ V => f（u, v） = - f（u, v）（反对称性）
C. ∀ v ∈ V - { s } => ∑ f（u，v） >= 0
（ 不满足基尔霍夫电压定律，即流守恒的特性 ，但是满足放宽条件下的流守恒特性 ）
8.算法注意点:
A. 余流的处理（excess handling）：
算法尽量将余流压入汇点 t，若是还有一部分余流无法达到 t，则将所有剩下的余流返回给源点 s。当∀ u ∈ V 有 excess（u） == 0，那么算法终止，且得到了最大流。
B. 有效的高度标签（height label）：已提过
9.算法基本操作:
A. 压入（ push（u, v） ）：
if { residual（u，v） > 0 && height（u）== height（v） + 1 }（仅对活性点操作）：delta = min（excess（u），residual（u, v） ）；f（u，v） += delta； f（v，u） -= delta；excess（u） -= delta； excess（v） += delta；
B. 重标记（ relabel（u） ）：
if{ ∀ v ∈ V && residual（u，v） > 0 }then{ 选择出高度最小的点 v; }height（u） = height（v） + 1；
压入，重标记中任一操作仅对活性点有效：
if（ residual（u，v） > 0 && height（u） == height（v） + 1 ）:push（u）;
otherwise :relabel for all residual（u，v）in RG;
10.算法优化:
+动态树 O(VE log(V2/E))；
11.实现代码:
#include <iostream>
#include <cstring>
using namespace std;const int MAX_SIZE = 100;
const int INF = 1 << 30;int capacityGraph[MAX_SIZE][MAX_SIZE];
int flowMap[MAX_SIZE][MAX_SIZE];
int height[MAX_SIZE];
int excess[MAX_SIZE];
int src, des;
int vertex_num, edge_num;void init()
{ memset( capacityGraph, 0, sizeof( capacityGraph ) );memset( flowMap, 0, sizeof( flowMap ) );memset( height, 0, sizeof( height ) );memset( excess, 0, sizeof( excess ) );cout << "Enter vertex num && edge num : ";cin >> vertex_num >> edge_num;for( int i = 1; i <= edge_num; ++i ){int start, end, cap;cout << "Enter start && end && capacity : ";cin >> start >> end >> cap;capacityGraph[start][end] = cap;}src = 1;des = vertex_num;height[src] = vertex_num;
}void preFlow()
{for( int i = src; i <= des; ++i ){if( capacityGraph[src][i] > 0 ){const int flow = capacityGraph[src][i];flowMap[src][i] += flow;flowMap[i][src] = - flowMap[src][i];excess[src] -= flow;excess[i] += flow;}}
}void push( int start, int end )
{int flow = min( excess[start], capacityGraph[start][end] - flowMap[start][end] );flowMap[start][end] += flow;flowMap[end][start] = -flowMap[start][end];excess[start] -= flow;excess[end] += flow;
}bool reLabel( int index )
{int minestHeight = INF;for( int i = src; i <= des; ++i ){if( capacityGraph[index][i] - flowMap[index][i] > 0 )minestHeight = min( minestHeight, height[i] );}if( minestHeight == INF ) return false;height[index] = minestHeight + 1;for( int i = src; i <= des; ++i ){if( excess[index] == 0 )break;if( height[i] == minestHeight && capacityGraph[index][i] > flowMap[index][i] )push( index, i );}return true;
}void pushReLabel()
{bool flag = true;preFlow();while( true ){if( flag == false ) break;flag = false;for( int i = src; i <= des - 1; ++i ){if( excess[i] > 0 ) flag = flag || reLabel( i );}}
}int main()
{init();pushReLabel();cout << "max flow : " << excess[des] << endl;return 0;
}
这篇关于压入与重标记算法（预流推进算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
