P4722 【模板】最大流加强版 / 预流推进题解

pldzy · 2022-02-19 11:48:23 · 题解

本题解侧重解释 \text{HLPP} 细节部分，而对于 \text{HLPP} 的详细思路等不会过多阐述。

UPDATE

2022.10.06：感谢@MiniLong大佬的提点与学术支持（hack 数据），对 hlpp() 函数进行了更改。

2024.01.10：开 long long。

\text{HLPP} 思路

按照众多大佬所说的那样，\text{HLPP} 就是将水流自源点一步一步地推到其他中转点，最后推向汇点，汇点累计的流量就是该网络的最大流。

注意，在此算法中，我们的目标是图中所有中转点最后存储的流量为 0。

在此过程中，为了防止 \text{TLE}，也就是避免两个点互相不停地将水流推来推去的情况，我们给每一个节点一个高度，像我们在 \text{dinic} 算法中所做的那样，每次保证是从当前层推向下一层。同时，也要保证每次从高度最高的节点向低处节点推流，节省时间（这也是使用优先队列的原因）。

那为什么它会比其他解决最大流问题的算法快呢？

首先，在这里我们只用运行一次 \text{bfs}，在给每一个节点初始了一个高度之后，后面如果它这个点储存的流传不出去了，也只需要针对它单独更改其高度即可。

其次，因为它是一步一步将流向下推，所以不用多次 \text{dfs} 去寻找增广路径。

代码实现细节解释

\text{bfs} 初始高度

相比先给每一个节点初始高度为 0，用 \text{dinic} 中的手段给每个节点的高度初始为它距离终点的最短距离，明显会大大地减少后期更新其高度的次数。

具体代码如下：

inline bool bfs()
{
    rep(i, 1, n) h[i] = inf;
    h[t] = 0, q.push(t);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = hd[u], v; i; i = e[i].nxt)
            if(e[i ^ 1].f and h[v = e[i].to] > h[u] + 1)
                h[v] = h[u] + 1, q.push(v);
    }
    return h[s] == inf ? 0 : 1;
}

为什么是 if(e[i ^ 1].f) 而不是 if(e[i].f) 呢？

要注意因为我们是从终点反向去给每个点初始高度的，所以这时候我们走的边都是反向边。而这里是判断该两点之间正向边的流量是否为 0。
为什么是 if(h[v] > h[u] + 1) 而不是 if(h[v] > h[u] - 1) 呢？

原因同上，因为我们在走反向边，此时 v 更靠近 s，高度更高。

\text{HLPP} 函数

inline int hlpp()
{
    if(!bfs()) return 0;
    h[s] = n;
    for(int i = hd[s], v, d; i; i = e[i].nxt)
    {
        if(d = e[i].f)
        {
            p[v = e[i].to] += d, p[s] -= d;
            e[i].f -= d, e[i ^ 1].f += d;
            if(v != s and v != t and !inq[v]) pq.push(v), inq[v] = 1;
        }
    }
    rep(i, 1, n) if(h[i] != inf) gap[h[i]] += 1;
    while(!pq.empty())
    {
        int u = pq.top();
        pq.pop(), inq[u] = 0, push(u);
        if(!p[u]) continue;
        if(h[u] != inf and !--gap[h[u]])
        {
            rep(i, 1, n) 
                if(i != s and i != t and h[i] > h[u] and h[i] < n + 1) 
                    h[i] = n + 1;
        }
        updt(u), gap[h[u]] += 1, pq.push(u), inq[u] = 1;
    }
    return p[t];
}

注：\text{push} 函数的作用是将当前点存储的流尽可能地推到下一层的节点。

if(!bfs()) return 0; 原因？

回看 \text{bfs} 函数代码，若最后 s 没有高度，就意味着无法从 t 走到 s，那么自然也就不存在最大流一说了。也因此要把 h[s] = n; 放在判断的后面了。
h[s] = n;

因为 s 是源点，对于它来说有无尽的流，目前暂时不存在有流要回到 s，只有自 s 将流往下推到其他点，所以目前它的高度要是最高的。
为什么在 \text{HLPP} 中还需要 gap[] 数组？

这个数组用来统计每一层当前节点数量。此时它的作用是判断当此层为空时的情况。若此层为空，意味着那些在这层以上的节点无法将流送到终点，所以要将这些流送回源点。

因为流是自高往低才能流，所以要将这些点的高度设在源点高度之上。

相对应的就是后面的这段代码了：
```
    if(!--gap[h[u]])
    {
        rep(i, 1, n) 
            if(i != s and i != t and h[i] > h[u] and h[i] < n + 1) 
                h[i] = n + 1;
    }
```
updt(u), gap[h[u]] += 1, pq.push(u), inq[u] = 1;

当节点 u 存储的流在尽可能推给下一层节点之后还有流剩时，要向将流送完，只有更改节点高度，才可能将所有流推出去。所以就有了以上的操作。
为什么是 if(h[u] != inf and !--gap[h[u]]) 而不是 if(!--gap[h[u]])？

因为 h_u 有可能没被更新到，还是 inf。

\text{push} 函数

inline void push(int nw)
{
    for(int i = hd[nw], v; i; i = e[i].nxt)
    {
        if(!p[nw]) return;
        if(h[v = e[i].to] + 1 != h[nw] or !e[i].f) continue;
        int d = min(p[nw], e[i].f);
        p[nw] -= d, p[v] += d, e[i].f -= d, e[i ^ 1].f += d;
        if(v != s and v != t and !inq[v]) 
            pq.push(v), inq[v] = 1;
    }
}

它的作用就是将当前节点的流尽可能地推向下一层的节点。

if(v != s and v != t and !inq[v]) pq.push(v), inq[v] = 1;

注意优先队列里，存放的是存储了若干流的中转点，所以每次推流之后都要让推向的那个节点在有限队列里。

\text{updt} 函数

inline void updt(int u)
{
    h[u] = inf;
    for(int i = hd[u], v; i; i = e[i].nxt)
    {
        if(e[i].f and h[v = e[i].to] + 1 < h[u])
            h[u] = h[v] + 1;
    }
}

它的作用是更改当前节点的高度。

为什么要取最小的高度？

我们之所以会更改它的高度，是因为它有剩余的一些流无法推出去了。所以将它的高度设为最低可能的高度，以保证它还能将剩余流推出去。

AC Code

整体代码：

#include<bits/stdc++.h>
using std::min;
using std::vector;
using std::queue;
using std::priority_queue;

#define int long long 
#define maxn 2005
#define maxm 200005
#define inf 2147483647
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
int n, m, s, t;
int cnt = 1, hd[maxn];
struct node{
    int to, nxt, f;
}e[maxm << 1];
int p[maxn], h[maxn], gap[maxm];
bool inq[maxn];
queue <int> q;
struct cmp{
    inline bool operator () (int a, int b) const//重写仿函数 
    {
        return h[a] < h[b];
    }
};
priority_queue <int, vector<int>, cmp> pq;
int u, v, w;

inline int read()
{
    int x = 1, s = 0;
    char ch = getchar();
    while(ch < '0' or ch > '9') {if(ch == '-') x = -1; ch = getchar();}
    while(ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return x * s;
}

inline void add(int u, int v, int w)
{
    e[++cnt] = (node){v, hd[u], w};
    hd[u] = cnt;
    e[++cnt] = (node){u, hd[v], 0};
    hd[v] = cnt;
}

inline bool bfs()
{
    rep(i, 1, n) h[i] = inf;
    h[t] = 0, q.push(t);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = hd[u], v; i; i = e[i].nxt)
            if(e[i ^ 1].f and h[v = e[i].to] > h[u] + 1)
                h[v] = h[u] + 1, q.push(v);
    }
    return h[s] == inf ? 0 : 1;
}

inline void push(int nw)
{
    for(int i = hd[nw], v; i; i = e[i].nxt)
    {
        if(!p[nw]) return;
        if(h[v = e[i].to] + 1 != h[nw] or !e[i].f) continue;
        int d = min(p[nw], e[i].f);
        p[nw] -= d, p[v] += d, e[i].f -= d, e[i ^ 1].f += d;
        if(v != s and v != t and !inq[v]) 
            pq.push(v), inq[v] = 1;
    }
}

inline void updt(int u)
{
    h[u] = inf;
    for(int i = hd[u], v; i; i = e[i].nxt)
    {
        if(e[i].f and h[v = e[i].to] + 1 < h[u])
            h[u] = h[v] + 1;
    }
}

inline int hlpp()
{
    if(!bfs()) return 0;
    h[s] = n;
    for(int i = hd[s], v, d; i; i = e[i].nxt)
    {
        if(d = e[i].f)
        {
            p[v = e[i].to] += d, p[s] -= d;
            e[i].f -= d, e[i ^ 1].f += d;
            if(v != s and v != t and !inq[v]) pq.push(v), inq[v] = 1;
        }
    }
    rep(i, 1, n) if(h[i] != inf) gap[h[i]] += 1;
    while(!pq.empty())
    {
        int u = pq.top();
        pq.pop(), inq[u] = 0, push(u);
        if(!p[u]) continue;
        if(h[u] != inf and !--gap[h[u]])
        {
            rep(i, 1, n) 
                if(i != s and i != t and h[i] > h[u] and h[i] < n + 1) 
                    h[i] = n + 1;
        }
        updt(u), gap[h[u]] += 1, pq.push(u), inq[u] = 1;
    }
    return p[t];
}

signed main()
{
    n = read(), m = read(), s = read(), t = read();
    rep(i, 1, m)
        u = read(), v = read(), w = read(), add(u, v, w);
    printf("%lld\n", hlpp());
    return 0;
}

感谢阅读。

辛苦管理员审核，若有问题烦请指出。

P4722 【模板】最大流 加强版 / 预流推进 题解