关于当前弧优化
  • 板块学术版
  • 楼主zhy137036世末TJOIer
  • 当前回复31
  • 已保存回复31
  • 发布时间2020/6/3 21:43
  • 上次更新2023/11/7 01:13:12
查看原帖
关于当前弧优化
178294
zhy137036世末TJOIer楼主2020/6/3 21:43

当前弧优化是啥啊,是 dfs 中的那个引用吗。据说 LOJ 的网络流板子卡不加当前弧优化的 Dinic,但是我把引用去掉也过了啊(比加上引用慢了一点,但还是跑得飞快)

传说中的引用:

#define int long long
int dfs(int u=S,int mx=1e18){
	if(u==T) return mx;
	int lst=mx;
	for(int&i=hd[u];i;i=nxt[i]){//就是这里
		int v=to[i];
		if(dep[v]!=dep[u]+1ll||!now[i]) continue;
		int t=dfs(v,min(lst,now[i]));
		if(!t) dep[v]=0ll;
		else { now[i]-=t; now[i^1ll]+=t; lst-=t; }
		if(!lst) break;
	}
	return mx-lst;
}

完整代码(加引用)
完整代码(不加引用)

2020/6/3 21:43
加载中...