请问dinic为什么这样优化就快得飞起

P3376 【模板】网络最大流

Yahbim @ 2021-07-31 15:50:07

代码:

ll dfs(int u,ll flow){
    if(u==t || !flow) return flow;
    ll res=0;
    for(int &i=headc[u];i;i=edge[i].nxt){
        int v=edge[i].to;ll &w=edge[i].w,&fw=edge[i^1].w;
        if(w && depth[v]==depth[u]+1){
            ll delta=dfs(v,min(w,flow));
            if(!delta) continue;
            w-=delta,fw+=delta;
            res+=delta,flow-=delta;
            if(flow==0) break;
        }
    }
    if(res==0) depth[u]=-1;
    return res;
}

其中

if(flow==0) break;

这一句,如果加了,就是57ms;如果没加,就是1.05s,差距相当大。但是,我在开头处有

if(u==t || !flow) return flow;

这一句,同样保证了流量为0的无贡献点不会搜下去。它们俩唯一的差别只在于几次int和几次加减法的有无,然而它们的时间开销真的有这么大么?


by 0htoAi @ 2021-07-31 16:06:07

因为这个break是内层循环里面的,而总所周知网络流一个点要连一堆边。你加了这个可能只需要跑几条边就退出,你不加就每次都得跑几十条边。


by 约瑟夫用脑玩 @ 2021-07-31 16:11:12

其实真正的原因应该是你加了当前负优化,如果flow=0 时不 break 掉后面的边这次增广都走不了了,于是增广次数大大增加,慢的堪比 FF


by 约瑟夫用脑玩 @ 2021-07-31 16:11:29

@Yahbim


by Yahbim @ 2021-07-31 16:42:22

@约瑟夫用脑玩 懂了,谢谢!


by Yahbim @ 2021-07-31 16:42:54

@hanhan_zz 知道了,谢谢qwq


by Ckger @ 2021-07-31 21:24:48

@Yahbim 原因是您太巨了(手动滑稽


by Yahbim @ 2021-07-31 22:04:13

@Ckger 捕捉


by Ckger @ 2021-07-31 23:08:16

@Yahbim 恭喜您捕捉到一枚蒟蒻


|