365体育网投世家先来怀疑一下斯算法的想想吧。大家先来怀疑一下者算法的思考吧。

思想

大家先来怀疑一下这个算法的思维吧:joy:

探访人家的讳——最高标号预留推进

多高端大气上档次2333333咳咳

于它们的名字被我们可以看,它的核心思想是—推进,而无是找增广路

这就是说它是怎落实推动的也?

良粗略,我们从源点开始,不停歇的通向其他的点加流量,对于每个点都这样操作。那么推到最后,我们不怕好拿走到达汇点的极其特别流量

 

但是也许会见现出同样种状态,就是$A$送流量为$B$,$B$觉得不好意思不思要,于是以助长为$A$,$A$非常热心就同时推为$B$……直到推到TLE为止。。那怎么化解这种情形呢?

咱们本着每个点,引入一个冲天$H$,并且确定,一个点$u$可以于其他一个点$v$送流量,当且仅当$H[u]=H[s]+1$

诸如此类咱们就算好管不见面有上面情况时有发生了

 

除此以外还有雷同种植状态,就是者点还是时有发生流量,但是迫于高度的界定流动不出来,那怎么处置为?

万分简单,我们多这点之莫大,这样这个点之流量就可知流动出来了。

 

吐槽

这算法。。

怎么说……..

学来也就是是装装13咔嚓。。。。

长得比EK丑

跑的比EK慢

写着比EK难

优化

养推进为不怕是这些情节了

然而其的名里之嵩标号凡啥意思呢?

此要感谢咱的熟人tarjan,他跟他的伴发现,如果老是选的触及是惊人最高的触发,时间复杂度会更美。

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

 

此外还有一个比较显著的优化,如果一个莫大$i$是匪在的,即图中莫惊人也$i$的触及,那么从比$i$高之触发得非会见活动至汇点$T$,因为根据我们的限制法,必须要透过高度也$i$的触发,于是这些点就算没有用了

优化

留下推进为便是这些情节了

只是它的讳里之高标号凡啥意思呢?

夫只要谢谢咱的熟人tarjan,他及他的同伴发现,如果老是挑的接触是莫大最高的触及,时间复杂度会重尽善尽美。

好优化及$O(n^2\sqrt{m})$

 

除此以外还有一个比明显的优化,如果一个高度$i$是匪在的,即图被尚无高度为$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;
}

 

思想

大家先来怀疑一下斯算法的想想吧:joy:

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

万般高端大气上档次2333333咳咳

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

这就是说她是怎落实推动的吧?

杀简单,我们打源点开始,不歇的往任何的点加流量,对于每个点还这么操作。那么推到最后,我们便得获得到达汇点的极端可怜流量

 

但也许会见起相同种状态,就是$A$送流量为$B$,$B$觉得不好意思不思量使,于是还要促进为$A$,$A$非常热情就又推为$B$……直到推到TLE为止。。那怎么化解这种状态吗?

咱们本着每个点,引入一个可观$H$,并且确定,一个点$u$可以往其他一个点$v$送流量,当且仅当$H[u]=H[s]+1$

这么我们尽管好包非会见生上面情况发生了

 

除此以外还有平等种植状况,就是这个点依然时有发生流量,但是迫于高度的限定流动不下,那怎么收拾呢?

不行简单,我们多这点之万丈,这样是点的流量就能流动出来了。

 

吐槽

夫算法。。

怎么说……..

学来也即是装装13咔嚓。。。。

长得比EK丑

跑的比EK慢

写着比EK难

代码

问题在这儿

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

#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;
}

 

相关文章