蒟蒻求助,关于写dinic时一个奇怪的现象
  • 板块学术版
  • 楼主ZZ作者
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/12/25 16:00
  • 上次更新2023/11/5 05:42:30
查看原帖
蒟蒻求助,关于写dinic时一个奇怪的现象
118743
ZZ作者楼主2020/12/25 16:00

之前写 dinicdinic 时都是这么写 dfsdfs 的:

inline ll dfs(ll u,ll fl){
	if(u==t)return fl;
	ll re=fl,i;
	for(i=cur[u];i&&re;i=nx[i]){
		if(d[to[i]]==d[u]+1&&w[i]){
			ll k=dfs(to[i],min(re,w[i]));
			if(!k)d[to[i]]=0;
			re-=k; w[i]-=k; w[i^1]+=k;
		}
	}
	cur[u]=i;
	return fl-re;
}

然后因为学校造了加强的数据做题的时候莫名一直在T,卡常的过程中偶然改成了这样:

inline ll dfs(ll u,ll fl){
	if(u==t)return fl;
	ll re=fl;
	//把i的定义放进循环了(其他都一样
	for(rint i=cur[u];i&&re;i=nx[i]){
		if(d[to[i]]==d[u]+1&&w[i]){
			ll k=dfs(to[i],min(re,w[i]));
			if(!k)d[to[i]]=0;
			re-=k; w[i]-=k; w[i^1]+=k;
		}
		cur[u]=i;
	}
	return fl-re;
}

然后: 7s0.5s7s\rightarrow 0.5s,窝整个人都傻了

本来以为可能是 ii 定义在循环里就会快,然后又这样写了一下:

inline ll dfs(ll u,ll fl){
	if(u==t)return fl;
	ll re=fl;
	for(rint i=cur[u];i&&re;i=nx[i],cur[u]=i){	//把当前弧优化放进for了
		if(d[to[i]]==d[u]+1&&w[i]){
			ll k=dfs(to[i],min(re,w[i]));
			if(!k)d[to[i]]=0;
			re-=k; w[i]-=k; w[i^1]+=k;
		}
	}
	return fl-re;
}

却发现跟原来差不多甚至慢了一点

有dalao知道这是怎么回事吗qaq蒟蒻不胜感激

2020/12/25 16:00
加载中...