比赛 2025暑期集训第4场 评测结果 A
题目名称 战略游戏 最终得分 100
用户昵称 pcx 运行时间 0.103 s
代码语言 C++ 内存使用 4.05 MiB
提交时间 2025-07-05 09:46:34
显示代码纯文本
#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<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;
}