请问dinic为什么这样优化就快得飞起
查看原帖
请问dinic为什么这样优化就快得飞起
372708
Yahbim楼主2021/7/31 15:50

代码:

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和几次加减法的有无,然而它们的时间开销真的有这么大么?

2021/7/31 15:50
加载中...