警示后人(70pts)
  • 板块P2712 摄像头
  • 楼主zymooll
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/11/12 10:23
  • 上次更新2023/10/27 03:18:52
查看原帖
警示后人(70pts)
289296
zymooll楼主2022/11/12 10:23

注意遍历点时,是要遍历每个点的位置,而不是其编号

例如以下示例代码有误:

signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		int u=read(),p=read();
		for(int j=1;j<=p;j++){
			int v=read();
			add_edge(u,v);
		}
	}
	int js=0;
	while(js!=n){
		int f=1;
		for(int i=1;i<=n;i++){
			if(in[i]==0){
				f=0,js++;
				for(int j=head[i];j;j=edge[j].next){
					in[edge[j].v]--;
				}
				in[i]=INT_MAX;
			}
		}
		if(f){
			cout<<n-js;
			return 0;
		}
	}
	cout<<"YES";
	return 0;
}

应改为:

signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		int u=read(),p=read();
		for(int j=1;j<=p;j++){
			int v=read();
			add_edge(u,v);
		}
		s.push_back(u);/*this*/
	}
	int js=0;
	while(js!=n){
		int f=1;
		for(int i:s){/*and this*/
			if(in[i]==0){
				f=0,js++;
				for(int j=head[i];j;j=edge[j].next){
					in[edge[j].v]--;
				}
				in[i]=INT_MAX;
			}
		}
		if(f){
			cout<<n-js;
			return 0;
		}
	}
	cout<<"YES";
	return 0;
}

2022/11/12 10:23
加载中...