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,几种情况都会触发,但最后一个未满的边保证不触发。结果跑得很慢。
不理解为什么和怎么写。