hlpp（欢乐婆婆）算法总结

突然发现咕了好久（X）

　　emm先大概说一下，hlpp是针对网络流算法的一种复杂度更优的算法，基于预流推进（即模拟）复杂度上界为 n²根号m 且跑不满

（所以学会了它，可以解决绝大部分dinic能解决的问题，以及绝大部分dinic不能解决的问题

先把以前的dinic算法放一下吧

你谷P3376 网络最大流模板

#include<bits/stdc++.h>

#define re register

using namespace std;

const int maxxx=(1ll<<)-;

inline int read()

{

    register int x=,f=; char ch=getchar();

    while(ch<''||ch>'') {if(ch=='-') f=-; ch=getchar();}

    while(ch>=''&&ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

struct node

{

    int to,nxt,dis;

}e[];

int head[],cur[],cnt=-;

void add(int u,int v,int w)

{

    e[++cnt].to=v;

    e[cnt].dis=w;

    e[cnt].nxt=head[u];

    head[u]=cnt;

}

int d[],n,m,s,t;

bool bfs()

{

    queue<int> q;

    q.push(s);

    memset(d,-,sizeof(d));

    d[s]=;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-;i=e[i].nxt)

        {

            int v=e[i].to;

            if(e[i].dis && d[v]==-)

            {

                d[v]=d[u]+;

                q.push(v);

            }

        }

    }

    return (d[t]!=-);

}

int dfs(int u,int flow)

{

    if(u==t) return flow;

    int tmp=,newflow;

    for(int i=cur[u ];i!=-;i=e[i].nxt)

    {

        int v=e[i].to;

        if(d[v]==d[u]+ && e[i].dis)

        {

            newflow=dfs(v,min(flow,e[i].dis));

            flow-=newflow;

            e[i].dis-=newflow;

            tmp+=newflow;

            e[i^].dis+=newflow;

            if(!flow) break;

        }

    }

    if(!tmp) d[u]=-;

    return tmp;

}

void dinic()

{

    int maxflow=;

    while(bfs())

    {

        for(re int i=;i<=n;++i) cur[i]=head[i];

        maxflow+=dfs(s,maxxx);

    }

    printf("%d\n",maxflow);

}

int main()

{

    memset(head,-,sizeof(head));

    n=read(); m=read(); s=read(); t=read();

    for(re int i=;i<=m;++i)

    {

        int x,y,z;

        x=read(); y=read(); z=read();

        add(x,y,z); add(y,x,);

    }

    dinic();

}

　　Dinic算法的基本思想就是找增广路，去进行流量增广的一种（贪心？）算法。然后为了能够保证正确性，反向给自己反悔的机会

（咱也不知道模拟费用流啥的算法是啥

　　但是这个HLPP算法呢，并不是基于增广路算法的网络流，而是基于另一种（贪心？）算法，去进行预流推进

（循环屁放了第二遍）

　　基本思想：

　　先说一下基本思想吧：这个算法是允许每个点储存一个流量的（超额流），不过要保证到了最后除了源点汇点以外的点超额流为0（达到动态平衡（笑））

　　所以为了每个节点储存的超额流能够推送出去，引入了高度的概念（越来越像模拟了）

　　同时在引入了高度后，就可以避免两个节点互相推送超额流的情况

　　不过，想一想，为什么，在现实生活中的水坑，就是一个例子，我们把超额流推给低的节点，结果有的水流就积攒到了这个水坑里，因为四周都比他高，而可怜的水坑

　　承受着巨大的超额流结果推送不出去，我们就死循环了。

　　所以咋办呢？　　要抬高这样的点的高度（废话

　　这个操作叫做重贴标签

　　（什么最小顶标和啊什么的我是完全不会

　　具体实现过程：

　　我们使用e[i]表示一个点的超额流，h[i]表示一个点的高度

　　从汇点开始进行bfs赋值高度（这里与网络流的分层图不同，为了保证可以流到汇点，必须让高度递增

　　每次处理高度最高且超额流不为0的点（用优先队列维护），并对其进行推流操作把所有能推的都尽量推出去，不用担心正确性，因为...

　　就算不对也可以让人家再退回来鸭！

　所以算法的正确性一目了然，和增广路的贪心反悔是相同的

　接下来如果e[u]还是不等于0，就要进行重贴标签，去抬高高度继续等待颓推流

　　最后如果除了源点汇点，其他超额流都是0，那么说明方案合法，此时汇点的超额流就是原图最大流

　　优化：

　　为了这个优秀的算法在实现时能完全优于增广路算法，加入一个船新优化（该优化比增广路中当前弧优化更优

　　GAP优化

　我们还可以发现如果一个点v在被重贴标签以后，如果它原来的高度已经没有其它点，那么高于它的点一定不能将流量推送到t了。

　　所以我们可以将高度大于h[v]且小于n+1的点高度设置为n+1，以便尽快将流量推送给s。

　　对于如何判断这个高度已经没有其它节点，可以和ISAP一样用一个gap数组来计数，这就是HLPP的gap优化。

　　具体实现：

#include<bits/stdc++.h>

#define re register

#define il inline

#define inc(i,j,k) for(re int i=j;i<=k;++i)

#define ra(i,u) for(re int i=head[u];i!=-1;i=a[i].nxt)

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

const int maxm=;

const int maxn=;

struct node

{

    int to,nxt,flow;

}a[maxm<<];

int head[maxn],gap[maxn],h[maxn],e[maxn];

bool vis[maxn];

int cnt=-,n,m,st,ed;

struct cmp {il bool operator () (int x,int y)const{return h[x]<h[y];}};

priority_queue<int,vector<int>,cmp> pq;

queue<int> q;

il void add(int u,int v,int w)

{

    a[++cnt].to=v;

    a[cnt].nxt=head[u];

    a[cnt].flow=w;

    head[u]=cnt;

}

il bool bfs()

{

    memset(h,inf,sizeof(h));

    h[ed]=;

    q.push(ed);

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

        ra(i,t)

        {

            int v=a[i].to;

            if(a[i^].flow && h[v]>h[t]+)

            {

                h[v]=h[t]+;

                q.push(v);

            }

        }

    }

    return h[st]!=inf;

}

il void push(int u)

{

    ra(i,u)

    {

        int v=a[i].to;

        if((a[i].flow) && (h[v]+==h[u]))

        {

            int df=min(e[u],a[i].flow);

            a[i].flow-=df;

            a[i^].flow+=df;

            e[u]-=df;

            e[v]+=df;

            if((v!=st)&&(v!=ed)&&(!vis[v]))

            {

                pq.push(v);

                vis[v]=;

            }

            if(!e[u])break;

        }

    }

}

il void relabel(int u)

{

    h[u]=inf;

    ra(i,u)

    {

        int v=a[i].to;

        if((a[i].flow)&&(h[v]+<h[u]))h[u]=h[v]+;

    }

}

inline int hlpp()

{

    if(!bfs())return ;

    h[st]=n;

    memset(gap,,sizeof(gap));

    inc(i,,n) if(h[i]!=inf)gap[h[i]]++;

    ra(i,st)

    {

        int v=a[i].to;

        if(int f=a[i].flow)

        {

            a[i].flow-=f;a[i^].flow+=f;

            e[st]-=f;e[v]+=f;

            if(v!=st&&v!=ed&&!vis[v])

            {

                pq.push(v);

                vis[v]=;

            }

        }

    }

    while(!pq.empty())

    {

        int t=pq.top();pq.pop();

        vis[t]=;push(t);

        if(e[t])

        {

            gap[h[t]]--;

            if(!gap[h[t]])

            {

                inc(v,,n)

                {

                    if(v!=st&&v!=ed&&h[v]>h[t]&&h[v]<n+)

                    {

                        h[v]=n+;

                    }

                }

            }

            relabel(t);gap[h[t]]++;

            pq.push(t);vis[t]=;

        }

    }

    return e[ed];

}

signed main()

{

    memset(head,-,sizeof(head));

    scanf("%d%d%d%d",&n,&m,&st,&ed);

    inc(i,,m)

    {

        int x,y;

        ll f;

        scanf("%d%d%lld",&x,&y,&f);

        add(x,y,f);

        add(y,x,);

    }

    ll maxf=hlpp();

    printf("%lld",maxf);

    return ;

}

这是我照着题解一点一点写的，例题的话等以后再更（窝就是太弱了

最大流——预流推进

巴特西

咕咕咕-HLPP算法

hlpp（欢乐婆婆）算法总结

突然发现咕了好久（X）

基本思想：

具体实现过程：

优化：

具体实现：

最新文章

热门文章