hbhz_zcy @ 2022-12-13 17:36:10
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,几种情况都会触发,但最后一个未满的边保证不触发。结果跑得很慢。
不理解为什么和怎么写。
by Z_302 @ 2022-12-13 17:41:51
Cu
by Alex_Wei @ 2022-12-13 17:42:16
@hbhz_zcy 这个错误太典了,问题出在于你直接引用 &i = head2[u]
,那么你是在 i = e[i].nxt
之后才判断 i && sum
的,所以若当前边没有流满但 sum
已经清零,你会跳过这条边,但实际上不应该跳过。
by hbhz_zcy @ 2022-12-13 17:48:19
我好像确实把判断顺序搞反了,第一遍意识到了这个问题但是第二编改的时候没改过来。