比赛 |
2025暑期集训第4场 |
评测结果 |
A |
题目名称 |
战略游戏 |
最终得分 |
100 |
用户昵称 |
淮淮清子 |
运行时间 |
0.094 s |
代码语言 |
C++ |
内存使用 |
3.91 MiB |
提交时间 |
2025-07-05 10:09:05 |
显示代码纯文本
#include<iostream>
using namespace std;
const int MAXN = 3005;
struct node{
int to, next;
}e[MAXN];
int h[MAXN], x[MAXN], tot = 0;
void add(int x, int y){
e[++ tot] = {y, h[x]};
h[x] = tot;
}
int n, dp[MAXN][2];
void dfs(int u, int fa){
dp[u][1] = 1, dp[u][0] = 0;
for(int i = h[u];i;i = e[i].next){
int to = e[i].to;
if(to == fa) continue;
dfs(to, u);
dp[u][0] += dp[to][1];
dp[u][1] += min(dp[to][1], dp[to][0]);
}
}
int main(){
freopen("strategic.in","r",stdin);
freopen("strategic.out","w",stdout);
cin.tie(0) -> ios::sync_with_stdio(0);
while(cin >> n){
for(int i = 0;i < n;i ++) h[i] = 0;
tot = 0;
for(int i = 0, id, sz;i < n;i ++){
char ls;
cin >> id >> ls >> ls >> sz >> ls;
for(int j = 1, x;j <= sz;j ++){
cin >> x;
add(id, x), add(x, id);
}
}
dfs(0, -1);
cout << min(dp[0][0], dp[0][1]) << '\n';
}
return 0;
}