比赛 2025暑期集训第4场 评测结果 A
题目名称 战略游戏 最终得分 100
用户昵称 KKZH 运行时间 0.109 s
代码语言 C++ 内存使用 4.14 MiB
提交时间 2025-07-05 10:54:16
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
long long n,m;
long long f[1510],dp[1510][2],z[1510],l[1510];
vector <long long> e[1510];
void dfs(long long u){
    dp[u][0]=0;
    dp[u][1]=1;
    for(long long i=0;i<e[u].size();i++) {
        long long v=e[u][i];
        dfs(v);
        dp[u][0]+=dp[v][1];
        dp[u][1]+=min(dp[v][0],dp[v][1]);
    }
}
int main(){
	freopen("strategic.in","r",stdin);
	freopen("strategic.out","w",stdout);
//	std::ios::sync_with_stdio(false);
	while(cin>>n){
		memset(f,0,sizeof(f));
		memset(dp,1,sizeof(dp));
		memset(z,1,sizeof(z));
		memset(l,0,sizeof(l));
		for(long long i=0;i<n;i++) e[i].clear();
		long long y,deep=0,x=0,r=0;
		long long a;
		for(long long i=0;i<n;i++){
			scanf("%lld:(%lld)",&a,&m);
			for(long long j=0;j<m;j++){
				scanf("%lld",&y);
				l[y]=1;
				e[a].push_back(y);
				f[y]=i;
			}
		}
		long long rt;
		for(long long i=0;i<n;i++)
			if(l[i]==0) {
				rt=i;
				continue;
			}
		dfs(rt);
		printf("%lld\n",min(dp[rt][0],dp[rt][1]));
	}
	return 0;
}