比赛 |
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;
}