在用 dinic 实现的费用流中:
ll dfs(int x,ll fl){
if(!fl||x==T)return fl;
ll an=0,ss;vis[x]=1;
for(int i=cur[x];i!=-1&&fl;i=e[i].nxt){
cur[x]=i;
if(d[x]+e[i].w==d[v]&&e[i].c>0&&!vis[v]){
ss=dfs(v,min(fl,e[i].c));
fl-=ss,an+=ss,mc+=(ss*e[i].w),e[i].c-=ss,e[i^1].c+=ss;
}
}
vis[x]=0;
if(!an)cur[x]=-1;
return an;
}
为防止 MLE,会用 vis 数组记录是否在搜索栈中,但是蒟蒻的 vis[x]=0 一行无论写不写都能 AC,想问下原因。