比赛 |
2025暑期集训第4场 |
评测结果 |
A |
题目名称 |
战略游戏 |
最终得分 |
100 |
用户昵称 |
对立猫猫对立 |
运行时间 |
0.106 s |
代码语言 |
C++ |
内存使用 |
4.12 MiB |
提交时间 |
2025-07-05 09:42:31 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
vector<int> g[1505];
int dp[1505][2];
void dfs(int u, int fa) {
dp[u][0] = 0;
dp[u][1] = 1;
for (int v : g[u]) {
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() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
freopen("strategic.in", "r", stdin);
freopen("strategic.out", "w", stdout);
int n;
while (scanf("%d", &n) != EOF) {
for (int i = 0; i < n; i++) g[i].clear();
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) {
int u, k;
scanf("%d:(%d)", &u, &k);
for (int j = 0; j < k; j++) {
int v;
scanf("%d", &v);
g[u].push_back(v);
g[v].push_back(u);
}
}
dfs(0, -1);
printf("%d\n", min(dp[0][0], dp[0][1]));
}
return 0;
}