网络流——最大流——HLPP学习笔记

· · 个人记录

前言

在刚了解最大流算法时，看到 Ford-Fulkerson（基于 DFS 求解增广路）（O(m\lvert f^*\rvert)）、Edmonds-Karp（O(nm^2)）、Dinic（O(n^2m)）这三个基于Ford–Fulkerson 增广的算法，复杂度都奇高无比。这毫无疑问预示着网络流能应付的数据规模十分有限。

所以，在学完 Edmonds-Karp 后，我认为应该学一些性能比较好的最大流算法（绝对不是因为我看不懂 Dinic）。于是，在 Oi-wiki 的最大流页面的最后，我找到了一个被普遍认为是复杂度最优的最大流算法——HLPP。

简介

不同于前面列举的三个算法，HLPP 求解最大流基于一种叫“预留推进算法”的东西。

超额流

预留推进算法不要求在求解过程中，流量始终保持守恒。它规定了某个节点的超额流 e(u)（我喜欢叫“溢出流量”）。其中：

e(u)=\sum_{(x,u)\in E}f(x,u)-\sum_{(u,y)\in E}f(u,y)

若 e(u)>0 则称结点 u 溢出。

高度函数

同时，预留推进算法规定结点的 h(u)，其中：

h(s)=n,h(t)=0;\forall (u,v)\in E_f,h(u)\le h(v)+1

推送（Push）

若结点 u 溢出，且存在结点 v 满足：

(u,v)\in E_f,c(u,v)-f(u,v)>0,h(u)=h(v)+1

则 u 可向 v 推送其溢出流量。可推送的最大值即为 \min\{e(u),c(u,v)-f(u,v)\}。

重贴标签（Relabel）

如果当前结点 u 无法高度使其无法向其余结点推送，而它又是溢出的，则需要对其重贴标签，即将 h(u) 改为 min_{(u,v)\in E_f}h(v)+1。

实现

那么，如何实现 HLPP 算法呢？

初始化除源点外所有结点高度为 0，特别地，h(s)=n。

首先推送 s（这里和之后讲的“推送”指的都是由结点 x 向 G_f 上所有 x 可推送的结点推送，直到 x 不再溢出），注意此次推送不考虑溢出流量 e(s) 的限制，因为 e(s) 可以为负；同时也不考虑高度差为 1 的限制。

接着，选出所有溢出结点中高度最小的那个 x，并推送 x。如果溢出流量没推送完，说明 x 需要重贴标签，直接重贴标签。

这样不停循环直到除源点、汇点外所有点都已不再溢出。此时 e(t) 即为最大流。

但是，这样写的话并不能达到最优复杂度，会跑得很慢。所以，我们要使用两个优化：BFS 优化和 GAP 优化。

BFS 优化

开头在反图上从 t 点 BFS 跑一遍最短路（边权为 1），令 h(i)(i\neq s) 为从 i 到 t 的最短路。同时判断 s,t 连通性，若不连通说明最大流为 0。

GAP 优化

因为推送条件是 h(u)=h(v)+1，所以若已不存在高度为 k 的结点，则所有 h(x)>k 的结点都绝对无法推送流至 t。这时，不妨重置 h(x)=n+1，使它能尽快将流推送回 s。

具体地，我们可以通过一个数组、一个桶来实现 GAP 优化。详见代码。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 205, maxm = 5e3 + 5, INF = 114514;

int n, m, s, t;
int head[maxn], nxt[maxm << 1], to[maxm << 1], cnt = 1;
ll flow[maxm << 1];
int hi[maxn];
ll ex[maxn], gap[maxn]; //hi：结点高度。ex：溢出流量。gap：高度为 i 的结点数量。 
stack<int> B[maxn]; //B：存储高度为 i 的 溢出 结点。 
int lev = 0; //lev：溢出 结点的最大高度。 

void merge(int u, int v, int w){
    nxt[++ cnt] = head[u];
    to[cnt] = v;
    flow[cnt] = w;
    head[u] = cnt;
}
void merge_flow(int u, int v, int w){
    merge(u, v, w);
    merge(v, u, 0);
}
bool push(int x){ //从结点 x 推送流。如果没推送完返回 true。 
    bool init = x == s; //标记是否正在初始化。
    for(int i = head[x]; i; i = nxt[i]){
        int j = to[i];
        if(!flow[i] || (!init && hi[x] != hi[j] + 1) || hi[j] == INF) continue; //该边流量为 0、未在初始化时当前点高度不是目标点加一、目标点高度无穷大都不能推送（注意初始化时不考虑高度差为 1）。 
        ll nw = init ? flow[i] : min(ex[x], flow[i]); //nw：可推送流量（注意初始化时不考虑源点溢出流量）。 
        if(j != s && j != t && !ex[j]) B[hi[j]].push(j), lev = max(lev, hi[j]); //若 j 点溢出，将其记录。 
        ex[x] -= nw, ex[j] += nw, flow[i] -= nw, flow[i ^ 1] += nw; //更新流量。 
        if(!ex[x]) return false;
    }
    return true;
}
void relabel(int x){ //重贴标签（即重置结点 x 的高度）。 
    hi[x] = INF; //先重置为无穷大。 
    for(int i = head[x]; i; i = nxt[i]){
        int j = to[i];
        if(flow[i]) hi[x] = min(hi[x], hi[j]); //在结点 x 能到达的结点中找到高度最小的。 
    }
    hi[x] ++; //高度要加 1。
    if(hi[x] < n){ //只处理高度小于 n 的结点。 
        B[hi[x]].push(x); //重新记录 x。 
        lev = max(lev, hi[x]);
        gap[hi[x]] ++;
    } 
}
bool bfs_init(){ //bfs 初始化高度。 
    for(int i = 1; i <= n; i ++) hi[i] = INF;  
    queue<int> q;
    q.push(t); //从汇点 t 开始跑 bfs。 
    hi[t] = 0; //汇点 t 高度为 0。 
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = head[x]; i; i = nxt[i]){
            int j = to[i];
            if(flow[i ^ 1] && hi[x] + 1 < hi[j]){
                hi[j] = hi[x] + 1;
                q.push(j);
            }
        }
    }
    return hi[s] != INF; //如果不连通则返回 false。 
}
int select(){ //选择高度最大的溢出结点。如果没有溢出结点说明程序结束，返回 0。 
    while(B[lev].empty() && lev >= 0) lev --;
    return lev == -1 ? 0 : B[lev].top();
}
ll HLPP(){
    if(!bfs_init()) return 0; //若图不连通，直接返回 0。
    for(int i = 1; i <= n; i ++) gap[i] = 0;
    for(int i = 1; i <= n; i ++) if(hi[i] != INF) gap[hi[i]] ++; //初始化 gap。 
    hi[s] = n; //源点 s 的高度定为 n。
    push(s); //初始化预流。
    int x = 0;
    while(x = select()){ //不断选出高度最大的溢出结点。 
        B[lev].pop(); //选出来的结点，要么不再溢出，要么需要重贴标签，故直接弹出。 
        if(push(x)){ //若推送后仍溢出。 
            gap[hi[x]] --; //x 的高度需要修改。
            if(!gap[hi[x]]){ //如果高度为 x 的点不存在了。 
                for(int i = 1; i <= n; i ++){
                    if(i != s && hi[i] > hi[x] && hi[i] < n + 1) hi[i] = n + 1; //根据 GAP 优化，当前高度为 hi[x] 的结点不存在了，所以所有高度大于 hi[x] 的结点不可能将溢出流推送至 t。 
                }
            }
            relabel(x); //此时需要重贴标签。 
        }
    }
    return ex[t]; //答案即为最后 t 点的溢出流量。 
}

int main(){
    scanf("%d %d %d %d", &n, &m, &s, &t);
    for(int i = 1; i <= m; i ++){
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        merge_flow(u, v, c);
    }
    printf("%lld", HLPP());
    return 0;
}

易错点