标准的当前弧优化是这样的:
for(int &i=cur[x];i;i=nxt[i]){
if(!v[i]||dis[to[i]]!=dis[x]+1) continue;
ll num=dfs(to[i],min(w,v[i]));
res+=num;
w-=num;
v[i]-=num;
v[i^1]+=num;
if(!w) break;
}
以下这种当前弧优化会 TLE:
for(int i=cur[x];i;i=cur[x]){
cur[x]=nxt[cur[x]];
if(!v[i]||dis[to[i]]!=dis[x]+1) continue;
ll num=dfs(to[i],min(w,v[i]));
res+=num;
w-=num;
v[i]-=num;
v[i^1]+=num;
if(!w) break;
}
按照我的理解,每次遍历到点 x 时,cur[x] 就会指向点 x 下一步需要走的边而不会发生重复。而事实上它跑的非常慢。
(这是为什么