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
其实真正的原因应该是你加了当前负优化,如果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 恭喜您捕捉到一枚蒟蒻