比赛 2025暑期集训第4场 评测结果 E
题目名称 战略游戏 最终得分 0
用户昵称 李金泽 运行时间 0.154 s
代码语言 C++ 内存使用 3.63 MiB
提交时间 2025-07-05 10:50:34
显示代码纯文本
#include<cstdio>
#include<vector>
#define N 1500
using namespace std;
int n,m,f[N][2],x,y;
vector<int>ve[N];
int min(int x,int y){return x<y?x:y;}
void dfs(int u,int fa)
{
	f[u][0]=0;f[u][1]=1;
	for(int i=0;i<ve[u].size();i++)
	{
		int v=ve[u][i];
		if(v==fa)continue;
		dfs(v,u);
		f[u][0]+=f[v][1];
		f[u][1]+=min(f[v][0],f[v][1]);
	}
}
int main(){
	freopen("strategic.in","r",stdin);freopen("strategic.out","w",stdout);
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;i++)ve[i].clear();
		for(int i=1;i<=n;i++)
		{
			scanf("%d:(%d)",&x,&m);x++; 
			for(int j=1;j<=m;j++)
				scanf("%d",&y),y++,ve[x].push_back(y),ve[y].push_back(x);
		}
		dfs(1,0);
		printf("%d\n",min(f[1][0],f[1][1]));
	}
	return 0;
}