比赛 2025暑期集训第4场 评测结果 E
题目名称 战略游戏 最终得分 0
用户昵称 李奇文 运行时间 0.153 s
代码语言 C++ 内存使用 3.39 MiB
提交时间 2025-07-05 11:09:28
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=1505;
int n,f[N][3];
vector<int> g[N];
void dfs(int x,int fa){
    f[x][1]=1;
    for(int i=0;i<g[x].size();i++){
        if(g[x][i]!=fa) dfs(g[x][i],x);
    }
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(v==fa) continue;
        f[x][0]+=f[v][1];
        f[x][1]+=min(f[v][0],f[v][1]);
    }
}
int main(){
	freopen("strategic.in","r",stdout);
	freopen("strategic.out","w",stdout);
	while(cin>>n){
		memset(f,0,sizeof(f));
		for(int i=0;i<=2*n;i++){
			g[i].clear();
		}
		for(int i=1;i<=n;i++){
     	    int x,k;
     	    scanf("%d:(%d)",&x,&k);
     	    x++;
        	for(int i=1;i<=k;i++){
            	int y;
            	scanf("%d",&y);
            	y++;
            	g[x].push_back(y);
            	g[y].push_back(x);
        	}
    	}
    	dfs(1,0);
    	printf("%d\n",min(f[1][0],f[1][1]));	
	}
    return 0;
}