记录编号	602741	评测结果	A
题目名称	2997.[POJ 1463]战略游戏	最终得分	100
用户昵称	pcx	是否通过	通过
代码语言	C++	运行时间	0.101 s
提交时间	2025-07-05 16:09:16	内存使用	4.07 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=2000;
int  n,a,b,dp[N][2];
bool ch[N];
vector<int> t[N];
void dfs(int u){
	dp[u][0]=0;dp[u][1]=1;
	for(int i=0;i<(int)t[u].size();i++){
		int v=t[u][i];
		dfs(v);
		dp[u][1]+=min(dp[v][0],dp[v][1]);
		dp[u][0]+=dp[v][1];
	}
	return;
}
int main(){
	freopen("strategic.in","r",stdin);
	freopen("strategic.out","w",stdout);
	for(;scanf("%d",&n)!=EOF;){
		memset(ch,0,sizeof(ch));
		for(int i=0;i<n;i++){
			t[i].clear();
		}
		for(int i=1;i<=n;i++){
			scanf("%d:(%d)",&a,&b);
			for(int j=1;j<=b;j++){
				int c=0;
				scanf("%d",&c);
				t[a].push_back(c);
				ch[c]=1;
			} 
		} 
	    int root=-1;
	    for(int i=0;i<n;i++){
	    	if(!ch[i]){
				root=i;
			}
		}
		dfs(root);
		printf("%d\n",min(dp[root][0],dp[root][1]));
	}
	return 0;
}