Dinic当前弧优化

P3376 【模板】网络最大流

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

我好像确实把判断顺序搞反了,第一遍意识到了这个问题但是第二编改的时候没改过来。


|