记录编号	602692	评测结果	A
题目名称	2997.[POJ 1463]战略游戏	最终得分	100
用户昵称	彭欣越	是否通过	通过
代码语言	C++	运行时间	0.179 s
提交时间	2025-07-05 14:58:32	内存使用	4.82 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010,M=20010;
int n,dp[M][10];
int head[M],tot;
struct edge {
	int v,nxt;
}e[M*2];
void add (int u,int v) {
	e[++tot].v=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void dfs (int u,int fa) {
	//cout << "qwq" <<endl;
	dp[u][1]=1,dp[u][0]=0;
	for (int i=head[u];i;i=e[i].nxt) {
	    int v=e[i].v;
	    if (v==fa) continue;
	    dfs(v,u);
	    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);
	//ios::sync_with_stdio(0);
	//cin.tie(0),cout.tie(0);
	//cout << int('0') <<endl;
	while (cin >> n) {
		memset(head,0,sizeof(head));
		memset(dp,0,sizeof(dp));
		tot=0;
		for (int i=1;i<=n;i++) {
		    int k,t; 
		    scanf("%d:(%d)",&k,&t);
			for (int j=1;j<=t;j++) {
				int v;
		        cin >> v;
		        add(k,v);
		        add(v,k);
			}
		}
		dfs(0,-1);
		cout << min(dp[0][0],dp[0][1]) <<endl;
	}
	return 0;
}