比赛 |
2025暑期集训第4场 |
评测结果 |
A |
题目名称 |
战略游戏 |
最终得分 |
100 |
用户昵称 |
OTTF |
运行时间 |
0.105 s |
代码语言 |
C++ |
内存使用 |
4.02 MiB |
提交时间 |
2025-07-05 09:38:06 |
显示代码纯文本
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 1515;
int n;
vector<int> tree[N];
int dp[N][2];
void dp1 (int now, int dad) {
int resDo = 0;
int resDont = 0;
for (auto son : tree[now]) {
if (son == dad) {
continue;
}
dp1 (son, now);
resDo += min (dp[son][0], dp[son][1]);
resDont += dp[son][1];
}
dp[now][1] = 1 + resDo;
dp[now][0] = resDont;
}
int main () {
freopen ("strategic.in", "r", stdin);
freopen ("strategic.out", "w", stdout);
while (cin >> n) {
for (int i = 1; i <= n; i++) {
tree[i].clear();
}
int u, m, v;
for (int i = 1; i <= n; i++) {
scanf ("%d:(%d)", &u, &m);
u++;
for (int j = 1; j <= m; j++) {
scanf ("%d", &v);
v++;
tree[u].push_back(v);
tree[v].push_back(u);
}
}
memset (dp, 0, sizeof (dp));
dp1 (1, 0);
cout << min (dp[1][0], dp[1][1]) << endl;
}
return 0;
}