关于网络流做法的一个疑问
查看原帖
关于网络流做法的一个疑问
407417
HerikoDeltana楼主2021/7/7 20:43

先放上两段代码,区别只有一行,已经标出:

LL Dinic(CI &x,LL flow)
{
    if(x==t or !flow) Heriko flow;
    int i;
    LL k,y,rst=flow;
    for(i=now[x];i and rst;i=r[i].nex)
    {
        y=r[i].to;
        if(dis[y]==dis[x]+1 and r[i].val)
        {
            k=Dinic(y,Hmin(rst,r[i].val));
            if(!k) {dis[y]=0;continue;}
            r[i].val-=k;
            r[i^1].val+=k;
            rst-=k;
        }
    }
    now[x]=i;
    Heriko flow-rst;
}
LL Dinic(CI &x,LL flow)
{
    if(x==t or !flow) Heriko flow;
    int i;
    LL k,y,rst=flow;
    for(i=now[x];i and rst;i=r[i].nex)
    {
        y=r[i].to;
        if(dis[y]==dis[x]+1 and r[i].val)
        {
            k=Dinic(y,Hmin(rst,r[i].val));
            if(!k) {dis[y]=0;continue;}
            r[i].val-=k;
            r[i^1].val+=k;
            rst-=k;
        }
        if(!rst) break;//这里
    }
    now[x]=i;
    Heriko flow-rst;
}

前者 TLE 两个点,后者 AC 了。

问题就是多出来的那句为什么会变快?

2021/7/7 20:43
加载中...