警示后人(10pts)
查看原帖
警示后人(10pts)
289296
zymooll楼主2022/11/10 13:36

这个不能在函数内将标记解除,需要在函数调用完后统一解除标记。

例如以下代码不合法:

void f(int x){
	vis[x]=1;
	node[x]++;
	for(int i=head[x];i;i=edge[i].next){
		int v=edge[i].v;
		if(!vis[v])f(v);
	}
	vis[x]=0;//标记不能在此处解除
}
...
for(int i=1;i<=k;i++){
	f(cow[i]);
}

需要修改为:

void f(int x){
	vis[x]=1;
	node[x]++;
	for(int i=head[x];i;i=edge[i].next){
		int v=edge[i].v;
		if(!vis[v])f(v);
	}
	//vis[x]=0;
}
...
for(int i=1;i<=k;i++){
	f(cow[i]);
	memset(vis,0,sizeof(vis));
}

相关解释:

因为在边数大于点数的图中,对于从 AA 走到 BB 这种问题,具有多种路径,但是题目仅要求求解能够走到的点的个数,故只需要求解能否走到(即仅要求走到一次即可),而在函数内部解除标记,则有可能多次走到,极大提高了时间复杂度。

2022/11/10 13:36
加载中...