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

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

例题：给定一个$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;
}