记录编号	602757	评测结果	A
题目名称	2997.[POJ 1463]战略游戏	最终得分	100
用户昵称	梧叶已同秋雨去	是否通过	通过
代码语言	C++	运行时间	0.292 s
提交时间	2025-07-05 16:37:49	内存使用	3.96 MiB

#include<bits/stdc++.h>
using namespace std;
int n,f[1505][2],nxt[2*15000],head[2*1505],to[2*15000]; 
int cnt;
void add(int a,int b){
	cnt++;
	nxt[cnt]=head[a];
	head[a]=cnt;
	to[cnt]=b;
}
void dfs(int a,int fa){
	
	f[a][0]=0;
	f[a][1]=1;
	for(int i=head[a];i;i=nxt[i]){
		int b=to[i];//cout<<1;
		if(b==fa)continue;
		dfs(b,a);
		f[a][0]+=f[b][1];
		f[a][1]+=min(f[b][0],f[b][1]);
	}
}
int main(){
	freopen("strategic.in","r",stdin);
	freopen("strategic.out","w",stdout);
	while(cin>>n){
		for(int i=1;i<=n;i++){
			int m,x;
			char s,ss,sss;
			cin>>x>>s>>ss>>m>>sss;
			for(int j=1;j<=m;j++){
				int y;
				cin>>y;
				add(x,y);
				add(y,x);
			}
		}
		dfs(0,-1);
		cout<<min(f[0][1],f[0][0])<<"\n";
		for(int i=1;i<=cnt;i++){
			nxt[i]=0;
			to[i]=0;
		} 
		for(int i=0;i<=n;i++){
			head[i]=0;
			f[i][0]=0;
			f[i][1]=0;
		}cnt=0;
	}
	
	return 0;
}