关于 Dinic 算法当前弧优化
  • 板块学术版
  • 楼主2024ing
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/8/5 16:07
  • 上次更新2025/8/5 18:46:17
查看原帖
关于 Dinic 算法当前弧优化
1112408
2024ing楼主2025/8/5 16:07

是否引用形式的当前弧优化比赋值的慢很多?
经测试其在某些数据下会导致 30 倍额外的运算次数。

//fast
for(int _=cur[u],v;~_&&f>0;_=o[_].nxt) if(o[_].w>0&&dis[u]+1==dis[v=o[_].v]){
			cur[u]=_,tmp=dfs(v,min(f,o[_].w)),sum+=tmp,o[_].w-=tmp,o[_^1].w+=tmp,f-=tmp;
		}

//slow
for(int &_=cur[u],v;~_&&f>0;_=o[_].nxt) if(o[_].w>0&&dis[u]+1==dis[v=o[_].v]){
			tmp=dfs(v,min(f,o[_].w)),sum+=tmp,o[_].w-=tmp,o[_^1].w+=tmp,f-=tmp;
		}

然而这不一样吗,为什么?

2025/8/5 16:07
加载中...