比赛 2025暑期集训第4场 评测结果 W
题目名称 战略游戏 最终得分 0
用户昵称 彭欣越 运行时间 0.568 s
代码语言 C++ 内存使用 4.06 MiB
提交时间 2025-07-05 12:26:02
显示代码纯文本
#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));
		tot=0;
		for (int i=1;i<=n;i++) {
		    string s;
		    cin >> s;
		    //cout << s <<endl;
		    int sum=0,k,t;
		    for (int j=0;j<s.size();j++) {
		    	if (s[j]==':') {
		    		cout << sum <<endl;
		    		k=sum;
		    		sum=0;
		    		continue;
				}
				if (s[j]=='(') {
					continue;
				}
				if (s[j]==')') {
					t=sum;
					sum=0;
					continue;
				}
				sum=sum*10+int(s[j])-48;
			}
			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;
}