【费用流】关于判断点是否在搜索栈中的一个疑问
查看原帖
【费用流】关于判断点是否在搜索栈中的一个疑问
484076
mcDinic楼主2023/8/16 13:57

在用 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;//该行写不写均能AC
	if(!an)cur[x]=-1;
	return an;
}

为防止 MLE,会用 vis 数组记录是否在搜索栈中,但是蒟蒻的 vis[x]=0 一行无论写不写都能 AC,想问下原因。

2023/8/16 13:57
加载中...