Dinic当前弧优化
查看原帖
Dinic当前弧优化
142549
hbhz_zcy楼主2022/12/13 17:36

rt,有两份很相似的代码,但是时间很不一样。

for(int i=head2[u];i&&sum>0;i=e[i].nxt){
	int v=e[i].to;if(d[v]!=d[u]+1||e[i].v>=e[i].xv)  continue;
	LL x=dfs(v,min(sum,(LL)e[i].xv-e[i].v));if(!x)  d[v]=-1;
	sum-=x;e[i].v+=x,e[i^1].v-=x;
	if(e[i].v==e[i].xv)  head2[u]=e[i].nxt;
}

跑84ms,只有在流满的时候把邻接表表头移到当前位置,但是流没更新到或不在同一层不会触发。

for(int &i=head2[u];i&∑i=e[i].nxt){
	int v=e[i].to;if(d[v]!=d[u]+1||e[i].v>=e[i].xv)  continue;
	LL x=dfs(v,min(sum,(LL)e[i].xv-e[i].v));if(!x)  d[v]=-1;
	sum-=x;e[i].v+=x,e[i^1].v-=x;
}

这个跑840ms,几种情况都会触发,但最后一个未满的边保证不触发。结果跑得很慢。
不理解为什么和怎么写。

2022/12/13 17:36
加载中...