P4722 题解

Symbolize · 2022-12-27 14:44:16 · 题解

前言

2024.1.11 update ：解决被 hack 的问题；增加了更多的补充说明；算法模拟样例过程的图；修改错别字。

HLPP 求网络最大流

先简单说说 HLPP 这个神仙般的算法，时间复杂度达到了惊人的 O(n^2\sqrt m)。

HLPP 预流推进算法，我们将网络理解成纵横交织的河道，源点是水库，汇点是运输目标，其余的节点就是转折区，有向边是河流。

那么它是如何实现的呢？我们允许网络在非汇点、源点的节点停留（也就是说这是一个一步一步实现的过程，并非像 Dinic 那样一口气从源点走到汇点，而是一种整体最优观念），那么对于每一个节点会拥有一个超额流（也称余流），我们用 ef_i 表示，那么我们的每个节点都要想办法将自己的超额流（如果你不是汇点那你肯定不需要留着，推送出去一定不劣），推送出去，这样才能使得我们的网络能够进入汇点 t。所以 t 最后剩下的超额流（我们会用高度 highh_t 来迫使汇点成为最低的点从而无法推送超额流），就是 s 到 t 的网络最大流（所有能够推送的已经推送了，不可能能够再推送超额流到 t 了）。

需要注意的是，为了推送不陷入死循环，我们引入每个节点的高度 highh_i。“水往低处流”，所以我们只允许从高处的节点将超额流推送给较低的点（高度的初始值由从 t 开始 bfs，被遍历到的次序决定）。高度是会改变的，如果一个节点因为高度低了而无法推送超额流那么我们就考虑提高他的高度，这个过程我们称为 重贴标签。

既然引入了 heighh，那就可以说说预流推进的本质了，预留推进实际上是在不断的改变 heighh 的值，让所有的流量从源点出发，最终汇到源点（有些可能到不了汇点，让它回到源点）或汇点，最终汇点流量最大。

记住一句话，走到死路不要紧，只要每次走的都是最优的路。

还有一点想要提一下，反向连接的边可以起到反悔的作用（让流量流回去）。

接下来，我将重点讲一讲预流推进的具体实现。

定义一个优先队列，以高度为优先，因为我们的推送过程是需要从高到低的（这样才能保证你在处理当前节点的时候不会还有别的节点可以给你推送超额流）。原本每个节点高度为 0,但是 s 的高度为 n，这样能保证源点能够将自己的余流推送给所有与他相接的节点。然后将所有的节点的余流设为 0，但是 s 的无穷大（不用担心多出来流量，走不到 t 的节点我们可以通过将高度设为 n+1 从而直接流回源点）。

考虑如何处理优先队列中的节点，我们开始处理优先队列中的队首 x，对他进行推送，那么如果推送结束后，当前节点还有超额流，那么我们就重贴标签，让当前节点的高度比他能到的所有节点的最低节点高 1（原因前文有提到），保证下次一定能够推送又不至于导致有节点未能被推送（因为有 highh_x+1=highh_{to} 一限制条件）。然后再次加入优先队列，等待下一次推送（这一系列的操作都是建立在还有余流的基础下的），因为已在队列中的节点不要重复入队，所以要使用一个 vis 标记数组。

然后说一下如何推送，遍历 x 的所有出边，若发现 highh_x+1=highh_{to}，那么这条边就可以进行推送(因为原定的顺序是 bfs 制定的所以说一开始的所有与 x 相邻的节点都会满足这个条件，而修改高度之后就不一定了，所以要求重贴标签必须将需进行重贴的节点的高度恰好比它所能够到达的高度最低的节点大 1)，每次的推送量显然不能超过允许通过的流量也不能多于当前节点超额流，所以有推送流量 d=\min(ef_x,w_i)，只要出现了流量的转移就必须要重新入队（如果已经在队列里就不用了），值得注意的就是反向边的允许通过流量一定要加上 d，不然就没法回头了。

补充一点，重贴标记如果失败就让他到源点上面去，由于重贴失败了，所以它一定能够流回源点。

最终 ef_t 就是网络最大流。

花了很长时间才将 luogu 样例的维护过程画了出来，但还是很丑，希望大家见谅，感性理解一下吧，特别是上面文字没完全明白的同学，重点注意薄荷绿五角星位置的流量出入与深紫色五角星节点的高度改变，搞清楚这个图那么这个算法就没什么太大问题。

优化：

可以使用 ISAP 的 gap 数组进行优化，这里就简单一提了。

非源点高度设为 0 会增加很多运行次数，把高度设为到 t 的距离明显能少跑很多。bfs 反向遍历一遍就可以了。

然后就是我们的 gap 数组优化了！我们发现如果一个节点，他它没有别的节点高，就一定无法使得流量到达 t。那把它提到 s 上端不就好了？它将直接流向 s，不会浪费操作次数，那如何判断呢？用 gap 存储每个高度的个数就可以了！

AC Code of Luogu P4722 【模板】最大流 加强版 / 预流推进

/*
    Luogu name: Symbolize
    Luogu uid: 672793
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=1e6+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
int n,m,s,t,e[N],h[N],ne[N],w[N],idx,highh[N],ef[N],gap[N],vis[N];
struct cmp{bool operator()(int a,int b)const{return highh[a]<highh[b];}};//手动定义排序规则 
priority_queue<int,vector<int>,cmp> q;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
void add(int x,int y,int z)
{
    idx+=2;//建立双向边 
    e[idx]=y;
    ne[idx]=h[x];
    w[idx]=z;
    h[x]=idx;
    e[idx+1]=x;
    ne[idx+1]=h[y];
    w[idx+1]=0;//反相边的权值为0
    h[y]=idx+1;
    return;
}
bool bfs()//bfs把初始的高度定义为到t的距离，s则为n 
{
    queue<int> q;
    memset(highh,0x3f,sizeof highh);
    highh[t]=0;//t的高度为0，起点 
    q.push(t);//从t开始 
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];~i;i=ne[i])
        {
            int to=e[i];
            if(w[i^1]/*剩余容量不为0*/&&highh[to]>highh[x]+1/*可以流向当前目标节点*/)
            {
                highh[to]=highh[x]+1;//更新高度 
                q.push(to);//进队 
            }
        }
    }
    //判断是否连通 
    if(highh[s]!=inf) return 1;
    return 0;
}
void push(int x)
{
    rep3(i,h,x,ne)
    {
        int to=e[i];
        if(w[i]/*剩余容量不为0*/&&highh[to]+1==highh[x]/*高度满足*/&&highh[to]<inf)
        {
            int d=min(ef[x],w[i]);//推送余留不得大于当前节点余流和剩余容量 
            w[i]-=d;//当前边的容量减掉 
            w[i^1]+=d;//方向边的流量加上 
            ef[x]-=d;//当前节点余留减少 
            ef[to]+=d;//增加目标余流 
            if(to!=s/*不为源点*/&&to!=t/*不为汇点*/&&!vis[to]/*不在优先队列中*/)
            {
                q.push(to);//加入优先队列等待推送
                vis[to]=1;//以加入优先队列 
            }
            if(!ef[x]) break;//没有余流了 
        }
    }
    return;
}
void relabel(int x)//重贴标签 
{
    highh[x]=inf;
    rep3(i,h,x,ne)
    {
        int to=e[i];
        if(w[i]/*剩余容量不为0*/&&highh[to]+1<highh[x]/*保证下一次可以推送即可，不要过高*/) highh[x]=highh[to]+1;
    }
    return;
}
int HLPP()//核心操作 
{
    if(!bfs()) return 0;
    highh[s]=n;//源点的高度为n 
    memset(gap,0,sizeof gap);
    rep1(i,1,n) if(highh[i]<inf/*没法到达的点就不用了*/) ++gap[highh[i]];//gap优化 
    //为了防止发生一些问题，单独跑一边源点 
    rep3(i,h,s,ne)
    {
        int to=e[i];
        int dist=w[i];
        if(dist&&highh[to]<inf)
        {
            w[i]-=dist;//当前边容量减少 
            w[i^1]+=dist;//反相边流量增加 
            ef[s]-=dist;//当前节点余流推送 
            ef[to]+=dist;//被推送节点余流增加 
            if(to!=s/*不为源点*/&&to!=t/*不为汇点*/&&!vis[to]/*不在优先队列中*/)
            {
                q.push(to);//等待推送 
                vis[to]=1;//已进入优先队列 
            }
        }
    }   
    while(!q.empty())
    {
        int x=q.top();//当前推送节点 
        vis[x]=0;//取消标记 
        q.pop();//出队 
        push(x);//推送 
        if(ef[x])//还有余流 
        {
            if(!--gap[highh[x]]/*如果本高度只有它一个*/) rep1(j,1,n) if(j!=s/*不为源点*/&&j!=t/*不为汇点*/&&highh[j]>highh[x]/*不可能被推送到汇点*/&&highh[j]<n+1/*高度不等于n+1*/) highh[j]=n+1;//把不可能到达汇点的所有点高度调为n+1，直接流向源点 
            relabel(x);//重贴标签，保证下次能够推送 
            ++gap[highh[x]];//新的高度 
            q.push(x);//因为还有余流所以进队 
            vis[x]=1;//标记 
        }
    }
    return ef[t];//返回汇点的余流，这就是网络最大流 
}
signed main()
{
    memset(h,-1,sizeof h);
    n=read();
    m=read();
    s=read();
    t=read();
    rep1(i,1,m) 
    {
        int u=read();
        int v=read();
        int w=read();
        add(u,v,w);//连边 
    }
    cout<<HLPP()<<endl;
    return 0;
}