为什么HLPP算法中使用GAP优化中的超额流能更快回到源点

HLPP算法（High-Level Preflow Push algorithm）是一种用于最大流问题的高效算法。其中，GAP（Gap Relabeling Algorithm）是一种超额流优化算法，可以提高算法的执行效率。

在GAP算法中，当一个节点的高度$h_v$被更新时，该节点成为了一个“孤立节点”。如果该节点到源点没有剩余容量，则该节点再也不会被用于最大流的计算中。因此，GAP算法将这些孤立节点标记为“gap”，并将它们从高度标签列表中删除。

当算法执行过程中，如果发现某个节点已经被标记为“gap”，则该节点可以被跳过，从而加快算法的执行速度。同时，将这些“gap”节点从高度标签列表中删除，可以使未访问的节点数量减少，从而减少了算法的时间复杂度。

在HLPP算法中，使用GAP优化中的超额流可以更快地回到源点，这是因为GAP算法可以减少未访问节点的数量，从而使超额流更快地回到源点。这样可以减少不必要的计算，提高算法的执行效率。

相关问题

最大流算法-最高标号预流推进(HLPP)

最高标号预流推进算法（High-Level Preflow Push, HLPP）是一种常用的最大流算法。它的基本思想是将节点按照高度分类，按照高度从高到低进行推进流量，同时维护一个优先队列，以保证高度最高的节点优先处理。该算法可以在$O(V^2\sqrt{E})$的时间复杂度内求解最大流，其中$V$和$E$分别表示节点数和边数。

算法的具体步骤如下：

1.初始化：将源点$s$的距离$d(s)$设为$|V|$，其余节点的距离$d(v)$设为$0$，并将源点的流量$f(s,v)$设为该边的容量$c(s,v)$。

2.进行预流推进：对于每一个非汇点$v\neq t$，如果$f(s,v)>0$，则将流量$f(s,v)$推进到邻接点中距离$d(v)$最小的点上去，如果邻接点的距离$d(u)=d(v)-1$，则可以推进的流量为$\delta=f(s,v)-f(v,u)$，否则可以推进的流量为$f(s,v)$。如果推进后$f(s,v)$变为$0$，则将节点$v$从高度$h$的桶中移除，并将其加入高度$h+1$的桶中。

3.进行流量推进：从高度最高的桶开始，对于每一个节点$v$，如果$f(s,v)>0$且存在一条从$v$出发的饱和边$(v,u)$，则将流量$\delta=\min(f(s,v),c(v,u)-f(v,u))$从$v$推进到$u$，如果推进后$f(v,u)=c(v,u)$，则将节点$v$从高度$h$的桶中移除，并将其加入高度$h+1$的桶中。

4.重贴标签：如果节点$v$的高度$d(v)$小于$|V|$，且存在一条从$v$出发的非饱和边$(v,u)$，则将节点$v$的高度$d(v)$更新为$d(u)+1$。

5.重复步骤3和4，直至无法再推进流量或者汇点$t$不再可达。

最终的最大流即为源点$s$流出的总流量。

最高标号预流推进算法的详细例题

下面以一个例题来说明最高标号预流推进算法的具体实现过程。

例题：给定一个$n$个点$m$条边的有向图，每条边有一个容量限制，求从源点$s$到汇点$t$的最大流。

输入格式：
第一行包含三个整数$n,m,s$，分别表示点数，边数和源点编号，其中$2\leq n\leq 10^4,1\leq m\leq 10^5$；
接下来$m$行，每行包含三个整数$a,b,c$，表示从$a$到$b$有一条容量为$c$的边，其中$1\leq a,b\leq n,1\leq c\leq 10^9$。

输出格式：
输出一个整数，表示最大流的大小。

输入样例：
4 5 1
1 2 2
1 3 3
2 3 1
2 4 1
3 4 2
输出样例：
3

算法实现：

首先，我们需要定义一个结构体来存储每条边的信息，包括边的起点、终点、容量和流量：

struct Edge
{
    int from, to, cap, flow;
    Edge(int u, int v, int c, int f):from(u),to(v),cap(c),flow(f){}
};

然后，我们需要实现一个函数`addEdge`来添加一条边，该函数将在建图时使用：

void addEdge(int from, int to, int cap)
{
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}

接下来，我们需要实现最高标号预流推进算法：

int HLPP(int s, int t)
{
    vector<int> h(n+1), e(n+1);  // h[i]表示节点i的高度，e[i]表示节点i的超额流量
    vector<int> cnt(n+1);  // cnt[i]表示高度为i的节点数量
    vector<vector<int>> H(n+1);  // H[i]表示高度为i的节点集合
    vector<int> vis(n+1);  // vis[i]表示节点i是否在队列中

    // 初始化
    for (int i = 0; i < m; i++)
        e[edges[i].from] += edges[i].cap;
    h[s] = n; vis[s] = vis[t] = 1;
    for (int i = 0; i < G[s].size(); i++)
    {
        int v = edges[G[s][i]].to;
        int d = edges[G[s][i]].cap;
        edges[G[s][i]].flow += d;
        edges[G[s][i]^1].flow -= d;
        e[v] += d;
        if (!vis[v] && v != t)
        {
            H[n-h[v]].push_back(v);
            cnt[n-h[v]]++;
            vis[v] = 1;
        }
    }

    // 预流推进
    for (int i = n-1; i >= 0; i--)
    {
        while (cnt[i])
        {
            int u = H[i][cnt[i]-1];
            bool flag = false;  // flag用于判断节点u是否可以推进流量
            for (int j = 0; j < G[u].size(); j++)
            {
                Edge &e = edges[G[u][j]];
                if (e.cap > e.flow && h[u] == h[e.to]+1)
                {
                    int delta = min(e.cap-e.flow, e[u]);
                    e.flow += delta;
                    edges[G[u][j]^1].flow -= delta;
                    e[u] -= delta;
                    e[e.to] += delta;
                    e-= delta;
                    e[e.to] += delta;
                    e-= delta;
                    if (e[u] > 0)
                    {
                        e-= e[u];
                        e[e.to] += e[u];
                        e[u] = 0;
                    }
                    if (e.cap > e.flow && !vis[e.to] && e.to != t)
                    {
                        H[n-h[e.to]].push_back(e.to);
                        cnt[n-h[e.to]]++;
                        vis[e.to] = 1;
                    }
                    flag = true;
                    if (--cnt[i] == 0)
                        break;
                }
            }
            if (!flag)
            {
                h[u]--;
                for (int j = 0; j < G[u].size(); j++)
                {
                    Edge &e = edges[G[u][j]];
                    if (e.cap > e.flow && h[u] == h[e.to]+1)
                    {
                        e[u] -= min(e.cap-e.flow, e[u]);
                        e[e.to] += min(e.cap-e.flow, e[u]);
                        if (e[u] == 0)
                            break;
                    }
                }
                if (e[u] > 0)
                {
                    H[n-h[u]].push_back(u);
                    cnt[n-h[u]]++;
                }
                else
                    vis[u] = 0;
            }
        }
    }
    return e[t];
}

最后，我们只需要在主函数中读入数据，建图并调用HLPP算法即可：

int main()
{
    // 读入数据
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        addEdge(a, b, c);
    }

    // 调用HLPP算法求解最大流
    int maxflow = HLPP(s, n);

    // 输出结果
    cout << maxflow << endl;

    return 0;
}