本文介绍一种求网络流最大流的高效算法：最高标号预流推进算法(HLPP)。这篇文章是网络流的延伸。

        HLPP算法并不是基于增广路的，它的思想是不断进行推流直到除了源点汇点外的点流量平衡，要了解这个算法需要先理解以下几个概念：

  • 额外流：这个点得到但未流出的总流量，存在额外流说明该点没有达到流量平衡。
  • 高度标号：HLPP算法采用的也是分层图思想。它要求结点只能将流推向比它高度小一的结点。这个要求的引入是因为不加限制可能会出现两个点轮番推流最后死循环的局面。

        HLPP算法中允许结点流量不平衡，即流入多于流出，这样的结点称为活动结点。算法中不断将结点中多余的流量推给其余的结点，将活动结点变成非活动结点。如果某个结点无法通过推流变成非活动结点，我们就需要更换其高度标号，这一步称为重贴标签。当所有非汇点源点均为非活动结点时算法结束，得到的就是最大流。普通预留推进算法用队列进行这个过程，但如果将队列换为优先队列（每次取高度最大的结点），就得到效率更高的最高标号预流推进算法。
        下面是HLPP算法步骤，HLPP算法同样在残量网络上进行。

  1. 用BFS算法从汇点开始进行标号（从0开始），这一步与ISAP算法基本相同。
  2. 将源点高度标记成n（n为结点数量）。
  3. 遍历源点每一条出边，将这些边的容量尽可能地利用，进行最大程度的推流，更新源点与出点的额外流，将其中额外流不为0并且不是源点汇点的结点入队。
  4. 不断取优先队列首元素并进行如下操作：遍历所有出边，对出边权值非0并且高度恰好减一的出点进行推流，推流量不得大于边权和额外流，更新两点的额外流和边权，新结点（不为源点汇点时）入队；当遍历完所有出边后若额外流仍存在，进行重新标号：遍历所有边权非0的出边，找到最小出点高度，该点高度更新成最小高度加一，重新入队。
  5. 队列为空时结束算法。

        下面是几点理解。
        我们第3步进行了源点最大程度的推流，易知最大流不可能多于这些流量，并且这些流量很可能有多余。但不必担心推流过多，这是因为多余的流会逆推回源点。也就是说，源点仅在第三步时向图中“释放了”尽可能多的流量，它们会尽可能多地流向汇点，多余的流量将被回推到源点。
        将源点高度标记为n（是当时的最高高度）是为了防止过早的回推。我们第三步时的推流是没有高度限制的，如果不修改源点高度可能会导致过早回推，但这些流量不可能再从源点流出（源点只在第3步推流），导致得到的答案往往小于实际答案。
        在任何情况下，源点和汇点都不会入队。这是因为源点在第三步已经完成了推流使命，它只需要等待接收多余的流即可，而汇点根本不需要推流（它本来就是吸收流量的）。
        从这里就可以理解HLPP算法的整体思想了：先尽可能地释放更多的流量，尽可能地推流，多余的推回源点。
        HLPP算法又是怎么实现推回源点的呢？当某个结点无法实现推流时，我们会修改它的高度标号以提高它的高度，最终使得这些无法推流的结点高度高于源点的高度n，从而实现回推。
        HLPP算法也有GAP优化。我们记录每一个高度对应的结点数量，当某一个高度没有结点（即出现断层时，理解与ISAP算法相同），说明断层两侧的汇点源点不可能再实现联系，这时像ISAP算法一样直接退出算法？并不，虽然断层两侧（源点所在的一侧和汇点所在的一侧）已经不可能有联系，位于源点所在侧的结点不可能再将流推到汇点所在的一侧，但是队列中可能还有能够推到汇点的结点（它们位于汇点所在的一侧），因此算法不能直接结束。那么如何实现优化？既然源点所在的一侧无法再向汇点推流，那么只能向源点逆推，我们不妨将它们其中高度不到n+1的结点的高度标号全部改成n+1，以加快逆推速度。这就是HLPP算法的GAP优化。
        下面给出加强模板题洛谷P4722的HLPP算法代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>

#define inf 0x7fffffff
using namespace std;

struct {
    int to, next;
    int v;
} edge[200005 * 2 + 10000];
int head[20000 + 5], cnt = 0, n, m, s, t, h[20000 + 5], gap[20005 * 3] = {0}, vis[20000 + 5];
int e[20000 + 5], tree[200005 * 2], size = 0;
//下面是堆的部分
void solve(int x) {
    int x1 = 2 * x, x2 = 2 * x + 1, maxnn = x;
    if (x1 <= size && h[tree[x1]] > h[tree[maxnn]])maxnn = x1;
    if (x2 <= size && h[tree[x2]] > h[tree[maxnn]])maxnn = x2;
    if (maxnn != x)swap(tree[maxnn], tree[x]), solve(maxnn);
}

void up(int x) {
    if (x == 1)return;
    if (h[tree[x / 2]] < h[tree[x]])swap(tree[x / 2], tree[x]), up(x / 2);
}

void addHeap(int x) {
    tree[++size] = x;
    up(size);
}

int top() {
    int t = tree[1];
    tree[1] = tree[size--];
    solve(1);
    return t;
}
//上面是堆的部分
int read() {//读入优化
    char e = getchar();
    int s = 0;
    while (e < '0' || e > '9')e = getchar();
    while (e >= '0' && e <= '9')s = s * 10 + e - '0', e = getchar();
    return s;
}

inline void add(int x, int y, int z) {//加边
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
}

int HLPP() {
    queue<int> Q;
    for (int i = 1; i <= n; i++)h[i] = inf;//高度初始化
    h[t] = 0;//汇点为0
    Q.push(t);
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        for (int i = head[now]; i != -1; i = edge[i].next) {
            if (edge[i ^ 1].v > 0 && h[edge[i].to] == inf)h[edge[i].to] = h[now] + 1, Q.push(edge[i].to);//BFS部分
        }
    }
    if (h[s] == inf)return 0;//源点高度未更新，说明不连通，返回0
    h[s] = n;//更新源点高度
    for (int i = 1; i <= n; i++)if (h[i] < inf)++gap[h[i]];//统计结点高度数目
    for (int i = head[s]; i != -1; i = edge[i].next) {//源点推流
        int d = edge[i].v;//找到这条边的权值
        if (d > 0) {//权值大于0
            edge[i].v -= d, edge[i ^ 1].v += d, e[s] -= d, e[edge[i].to] += d;//更新额外流和权值，别忘了反边
            if (edge[i].to != s && edge[i].to != t && !vis[edge[i].to])//入堆
                addHeap(edge[i].to), vis[edge[i].to] = 1;
        }
    }
    while (size > 0) {//堆非空时
        int now = top();
        vis[now] = 0;
        for (int i = head[now]; i != -1; i = edge[i].next) {
            if (edge[i].v > 0 && h[edge[i].to] + 1 == h[now]) {
                int d = min(e[now], edge[i].v);//找到最大推流量
                edge[i].v -= d, edge[i ^ 1].v += d, e[now] -= d, e[edge[i].to] += d;//更新
                if (edge[i].to != s && edge[i].to != t && !vis[edge[i].to])addHeap(edge[i].to), vis[edge[i].to] = 1;//入堆
                if (!e[now])break;//推流完成，结束
            }
        }
        if (e[now]) {//推流未成功，更新标号
            if (!--gap[h[now]]) {//如果出现断层
                for (int i = 1; i <= n; i++) {
                    if (i != s && i != t && h[i] > h[now] && h[i] < n + 1)//高于h[now]的点（就是断层中源点所在的一侧）更新高度
                        h[i] = n + 1;
                }
            }
            h[now] = inf;
            for (int i = head[now]; i != -1; i = edge[i].next) {//更新高度
                if (edge[i].v > 0)h[now] = min(h[edge[i].to] + 1, h[now]);
            }
            gap[h[now]]++, addHeap(now), vis[now] = 1;//重新入堆
        }
    }
    return e[t];//汇点额外流就是答案
}

int main() {
    n = read(), m = read(), s = read(), t = read();
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int j = 1; j <= m; j++) {
        int x, y, z;
        x = read(), y = read(), z = read();
        add(x, y, z), add(y, x, 0);
    }
    cout << HLPP();
    return 0;
}