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

bsdsdb · 2024-06-19 20:14:37 · 题解

Push-Relabel 预流推进算法

I have decided to write a tutorial on a topic not even Um_nik knows! (source)

与增广算法不同，预流推进会暂时忽略流的守恒性，让节点暂时储存流。

对节点定义一个「高度」h，其中 h(s)=n,h(t)=0. 算法只会在满足 h(u)=h(v)+1 的边 (u,v) 上执行「推送」操作。同时对每个节点 u 维护其「超额流」并记作 e(u)，表示这个点储存的流量，即 e(u)=\sum_{x\in V}f(x,u)-\sum_{x\in V}f(u,x). 称节点 u 溢出，当且仅当 e(u)>0. 特别的，s,t 不溢出。在算法运行过程中，除 s 外的所有节点 u 应保持 e(u)\ge 0.

推送（Push）操作：对于边 (u,v)，如果 u 溢出，则尽可能地将 u 中的超额流推送到 t.

重贴标签（Relabel）操作：对于节点 u，如果 u 溢出且没有可以执行推送的边，则将 h(u) 设为 \min_{(u,v)\in E}h(v)+1，即最小的可以执行推送操作的高度。该操作一定会增大 h(u)，并且这是除初始化之外唯一可以改变节点高度的操作。

算法的流程就是先对 s 的所有出边执行推送，然后不断寻找溢出节点，执行推送。如果推送完仍溢出，就重贴标签。

正确性证明：如果有点要将高度抬到 n+1 才能推流，并且除了 s 之外还能向外推流，那么离 t 最近的节点高度最低也是 4，矛盾。

HLPP (Highest Label Preflow Push) 算法

与上文所述的「不断寻找溢出节点」略有不同，HLPP 算法每次都会寻找溢出节点中高度最高的进行操作（详见代码），其复杂度为 O(n^2\sqrt{m}).

复杂度证明：

将算法分为 Push，Relabel，选择最高节点三部分进行复杂度分析。

每个节点最高的高度是 2n-1，Relabel 操作只对 n-2 个节点生效，因此 Relabel 操作的总复杂度是 O(n^2) 的。

对于 Push 操作，我们定义一个 Push f操作是「饱和的」当且仅当 Push 操作执行完后，这条边满流，否则就是「不饱和的」. 饱和的 Push 的数量是 O(nm) 的（考虑两个有连边的节点 u 和 v. 当在边 (u,v) 上进行了一次饱和的Push之后，想要在 (v,u) 上再进行一次，就至少要将 v 的高度增加 2，而每个节点的高度只被增加 O(n) 次）。

对于不饱和的 Push，我们定义一个溢出节点的「势能」是所有高度不超过自己（包括自己，包括非溢出节点）的节点个数，即 pot_u=|\{v|v\in V,h(v)\le h(u)\}|，「总势能」是所有溢出节点的势能之和，即 P=\sum_{e(u)>0}pot_u. 在一次对最高的节点的不饱和的 Push 之后，总势能会减小不比它高的节点的个数（在不饱和的 Push 之后，这个节点肯定不溢出）。在一次饱和的 Push 之后，总势能增加量一定小于 n（比他高的溢出节点个数加上不比他高的节点个数）。一次 Relabel 操作也会使总势能最多增加 n，因此总势能的总增加量是 O(n^2m) 的。在算法还未运行以及算法结束时，总势能都为 0（都没有溢出节点），因此不饱和的Push提供的总势能减小量也应该是 O(n^2m) 的。

定义一个「阶段」是指在最高的溢出节点不发生改变时进行的所有操作的集合。一个阶段中每个节点只会产生一次不饱和的 Push（如果多于一次，那么这个节点一定是推了又被推从而溢出，说明有比最高溢出节点高的溢出节点，矛盾），一次 HLPP 的阶段数量是 O(n^2) 的（证明：定义 h* 为最高溢出节点的高度，即 h*=\max_{e(u)>0}h(u). h* 增加一定是由于Relabel操作，且初始和结束时 h* 都为 0. Relabel的次数是 O(n^2) 的，因此 h* 最多增加 O(n^2)，减少 O(n^2)，共改变 O(n^2) 次）。定义一个阶段是「大」的，当且仅当它包含至少 k 个不饱和的 Push，否则是「小」的。所有小阶段的不饱和的 Push 总次数是 O(n^2k) 的。

在大阶段中高度为 h* 的节点至少有 k 个，因为所有的push都是选择高度最高的节点进行的。每当一个高度为 h* 的节点从溢出变得不溢出时，它对总势能的贡献都减少了 k，因为它自己的势能至少有 k. 因此大阶段的不饱和的Push数量是 O(n^2m/k) 的。取 k=\sqrt{m}，则所有不饱和的Push的数量是 O(n^2\sqrt{m}+n^2m/\sqrt{m})=O(n^2\sqrt{m}) 的。

对于寻找最高节点的操作，我们维护 h_m（初始为 0）和 2n-1 个栈（其实也可以是其它的数据结构，如队列，但是要求 O(1) 插入，删除，给出一个在这个数据结构里的数）B_1,\cdots,B_{2n-1}，其中 B_i 存储高度为 i 的所有节点，h_m 代表「我们以为的」h*. 在 Relabel 和 Push 时可以进行 h_m 的维护，即如果这个节点 Relabel 之后的高度或 Push 产生的新的溢出节点的高度超过 h_m，就更新 h_m（在Push时的更新仅在初始化时起作用）. 我们遗漏了 h* 下降的情况，但 h* 上升的情况全部考虑到了，因此 h_m\ge h*. 当 B_{h_m} 不为空时，B_{h_m} 中的一个点就是我们想要的「高度最高的溢出节点」。如果 B_{h_m} 不为空，就将 h_m 减 1，直到 B_{h_m} 不为空。执行这一操作当且仅当 h* 下降，因此这一操作的总复杂度是 O(n^2) 的，所以寻找最高节点的复杂度是 O(n^2) 的。

总复杂度即为 O(n^2+n^2+nm+n^2\sqrt{m})=O(n^2\sqrt{m}).

复杂度证明相关参考资料：

Levent Tunqel, On the Complexity of Preflow-Push Algorithms for Maximum-Flow Problems（总述算法流程，复杂度证明篇幅较长）

Tarjan, Analysis of the Highest-Label Push-Relabel Algorithm（简要证明复杂度，但不完整）

Joseph Cheriyan and Kurt Mehlhorn, An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow Algorithm（简要且完整地证明了不饱和的Push的数量是 O(n^2\sqrt{m}) 的）

Andrew V. Goldberg and Robert E. Tarjan, A New Approach to the Maximum-Flow Problem（第 7-8 页证明饱和的Push的数量是 O(nm) 的）

一些常数优化：

• BFS优化

即初始将所有点的高度都设为到 t 的距离，以减少 Relabel 的次数。

typedef long long ll;

ll s, t, ex[MAXN + 5] = {}, ht[MAXN + 5], hmx = 0; // 超额流，高度，处于该高度的节点的个数，最高高度 
vector<Edge> e[MAXN + 5];
stack<ll> B[MAXN * 2 + 5]; // 有哪些溢出节点处于该高度 

void addEdge(ll u, ll v, ll w) {
    e[u].push_back(Edge(v, w, e[v].size()));
    e[v].push_back(Edge(u, 0, e[u].size() - 1));
}
bool push(ll u, bool ini = 0) { // 如果处在初始化阶段，则忽略高度和超额流 返回推完之后是否仍然溢出 
    for (Edge& i : e[u]) {
        if (i.val == 0 || (!ini && ht[i.to] != ht[u] - 1) || ht[i.to] == inf) {
            continue;
        }
        ll ps = ini ? i.val : min(i.val, ex[u]); // 要推的流
        if (i.to != s && i.to != t && ex[i.to] == 0) {
            B[ht[i.to]].push(i.to);
            hmx = max(hmx, ht[i.to]);
        }
        ex[i.to] += ps;
        ex[u] -= ps;
        i.val -= ps;
        e[i.to][i.rev].val += ps;
        if (ex[u] == 0) {
            return 0;
        }
    }
    return 1;
}
void relabel(ll u) {
    ht[u] = inf;
    for (Edge i : e[u]) {
        if (i.val == 0) {
            continue;
        }
        ht[u] = min(ht[u], ht[i.to] + 1);
    }
    if (ht[u] != inf) {
        B[ht[u]].push(u);
        hmx = max(hmx, ht[u]);
    } 
}
bool bfs_init() {
    memset(ht, inf, sizeof ht);
    ht[t] = 0;
    queue<ll> q;
    q.push(t);
    while (!q.empty()) {
        ll h = q.front();
        q.pop();
        for (Edge i : e[h]) {
            if (ht[i.to] != inf || i.val != 0) { // 反向bfs，因此只走容量为0的边 
                continue;
            }
            q.push(i.to);
            ht[i.to] = ht[h] + 1;
        }
    }
    if (ht[s] == inf) {
        return 0;
    } else {
        ht[s] = n;
        return 1;
    }
}
ll select() {
    while (hmx >= 0 && B[hmx].empty()) {
        hmx--;
    }
    if (hmx >= 0) {
        ll ret = B[hmx].top();
        B[hmx].pop();
        return ret;
    } else {
        return -1;
    }
}
ll maxFlow() {
    if (!bfs_init()) { // s->t无路径，返回0 
        return 0;
    }
    push(s, 1); // 初始化
    ll u;
    while ((u = select()) != -1) {
        if (push(u)) { // 仍然溢出，则relabel 
            relabel(u);
        }
    } 
    return ex[t];
}