对当前弧优化的疑惑
查看原帖
对当前弧优化的疑惑
434015
Calanosay楼主2021/4/20 19:54
bool bfs(){
	queue<int> q;
	q.push(s);
	memset(dis,-1,(n+1)*sizeof(int));
	dis[s]=0;
	noww[s]=head[s];
	while(!q.empty()){
		int node=q.front();q.pop();
		for(int i=head[node];i!=-1;i=nex[i]){
			int to=v[i];
			if(dis[to]==-1&&w[i]){
				dis[to]=dis[node]+1;
				q.push(to);
				noww[to]=head[to];
			}
		}
	}
	return dis[t]!=-1;
}
ll dfs(int x,ll flo){
	if(x==t)	return flo;
	ll now=flo;
	for(int i=noww[x];i!=-1;i=nex[i]){
		noww[x]=i;
		int to=v[i];
		if(dis[to]==(dis[x]+1)&&w[i]){
			ll d=dfs(to,min(now,w[i]));
			now-=d;
			w[i]-=d,w[i^1]+=d;
			if(!now)	break;
		}
	}
	return flo-now;
}

每次dfs通一条路之后now数组都会重置,但是在你dfs的时候不是只会一直往下面搜索吗,我理解now数组的作用是在你遍历到now[x],x这个结点的时候起到一个传送作用,但是既然你是一直往后搜索,等于你dfs之后无法再次遍历到x这个结点了,也就是无法传送了。。所以我哪里理解有错误,这个优化明明很好,但我不理解

2021/4/20 19:54
加载中...