专栏首页数据结构与算法网络最大流算法—最高标号预流推进HLPP

网络最大流算法—最高标号预流推进HLPP

吐槽

这个算法。。

怎么说........

学来也就是装装13吧。。。。

长得比EK丑

跑的比EK慢

写着比EK难

思想

大家先来猜一下这个算法的思想吧:joy:

看看人家的名字——最高标号预留推进

多么高端大气上档次2333333咳咳

从它的名字中我们可以看出,它的核心思想是—推进,而不是找增广路

那么它是怎么实现推进的呢?

很简单,我们从源点开始,不停的向其他的点加流量,对于每个点都如此操作。那么推到最后,我们就可以得到到达汇点的最大流量

不过可能会出现一种情况,就是A送流量给B,B觉得不好意思不想要,于是又推给A,A非常热情便又推给B……直到推到TLE为止。。那怎么解决这种情况呢?

我们对每个点,引入一个高度H,并且规定,一个点u可以向另一个点v送流量,当且仅当H[u]=H[s]+1

这样我们就可以保证不会有上面情况发生了

另外还有一种情况,就是这个点依然有流量,但是迫于高度的限制流不出去,那怎么办呢?

很简单,我们增加这个点的高度,这样这个点的流量就能流出去了。

优化

预留推进也就是这些内容了

但是它的名字里的最高标号是啥意思呢?

这个要感谢咱们的熟人tarjan,他和他的小伙伴发现,如果每次选的点是高度最高的点,时间复杂度会更优。

可以优化至O(n^2\sqrt{m})

另外还有一个比较显然的优化,如果一个高度i是不存在的,即图中没有高度为i的点,那么从比高的点一定不会走到汇点T,因为根据我们的限制条件,必须要经过高度为i的点,于是这些点就没有用了

代码

题目在这儿

不是我说,这个算法真的是死慢死慢的,,,,

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN=2*1e3+10;
const int INF=1e8+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
int N,M,S,T;
int H[MAXN];//每个节点的高度
int F[MAXN];//每个节点可以流出的流量
int gap[MAXN];//每个高度的数量 
struct node
{
    int u,v,flow,nxt;
}edge[MAXN];
int head[MAXN];
int num=0;//注意这里num必须从0开始 
inline void add_edge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].flow=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
inline void AddEdge(int x,int y,int z)
{
    add_edge(x,y,z);
    add_edge(y,x,0);//注意这里别忘了加反向边 
}
struct comp
{
    int pos,h;
    comp(int pos=0,int h=0):pos(pos),h(h) {}
    inline bool operator < (const comp &a) const {return h<a.h;} 
};
priority_queue<comp>q;
bool Work(int u,int v,int id)
{
    int val=min(F[u],edge[id].flow);
    edge[id].flow-=val;edge[id^1].flow+=val;
    F[u]-=val;F[v]+=val;
    return val;
}
inline int HLPP()
{
    H[S]=N;F[S]=INF;q.push(comp(S,H[S]));
    while(q.size()!=0)
    {
        int p=q.top().pos;q.pop();
        if(!F[p]) continue;
        for(int i=head[p];i!=-1;i=edge[i].nxt)
            if( (p==S||H[edge[i].v]+1==H[p]) && Work(p,edge[i].v,i) && edge[i].v!=S && edge[i].v!=T)
                q.push( comp(edge[i].v,H[edge[i].v]) );
        if(p!=S && p!=T && F[p])
        {
            if( (--gap[ H[p] ])==0 )//该高度不存在 
            {
                for(int i=1;i<=N;i++)
                    if( H[p]<H[i]&&H[i]<=N && p!=S && p!=T ) 
                        H[i]=N+1;//设置为不可访问 
            }
            ++gap[ ++H[p] ];//高度+1 
            q.push( comp(p,H[p]) );
        }
    }
    return F[T];
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif 
    memset(head,-1,sizeof(head));
    N=read(),M=read(),S=read(),T=read();
    for(int i=1;i<=M;i++)
    {
        int x=read(),y=read(),z=read();
        AddEdge(x,y,z); 
    }
    printf("%d", HLPP() ); 
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P1991 无线通讯网

    题目描述 国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络; 每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。 任意...

    attack
  • 9.21模拟赛解题报告

    上来看T1,咦?我好像做过这题在仙人掌上的版本。。树上更简单吧。。写+拍 1h,期间拍出了暴力的两个bug。。。

    attack
  • 邻接表模板

    l邻接表的处理方法是这样: l图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过数组可以较容易地读取顶点信息,更加方便。 l图中每个顶点Vi的...

    attack
  • P1991 无线通讯网

    题目描述 国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络; 每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。 任意...

    attack
  • 9.21模拟赛解题报告

    上来看T1,咦?我好像做过这题在仙人掌上的版本。。树上更简单吧。。写+拍 1h,期间拍出了暴力的两个bug。。。

    attack
  • 邻接表模板

    l邻接表的处理方法是这样: l图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过数组可以较容易地读取顶点信息,更加方便。 l图中每个顶点Vi的...

    attack
  • 洛谷P2312 解方程(暴力)

    对于\(a[i]\)取模之后再判断就行了。注意判断可能会出现误差,可以多找几个模数

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题6-2 使用函数求特殊a串数列和

    给定两个均不超过9的正整数a和n,要求编写函数求a+aa+aaa++⋯+aa⋯a(n个a)之和。

    C you again 的博客
  • 排序算法——一篇文章搞懂常用的排序算法

    排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记...

    海盗船长
  • c语言之指向函数的指针

    绝命生

扫码关注云+社区

领取腾讯云代金券