比赛 |
2025暑期集训第4场 |
评测结果 |
W |
题目名称 |
战略游戏 |
最终得分 |
0 |
用户昵称 |
LikableP |
运行时间 |
0.068 s |
代码语言 |
C++ |
内存使用 |
1.75 MiB |
提交时间 |
2025-07-05 09:06:49 |
显示代码纯文本
#include <cstdio>
#include <cstring>
template <typename T> T read();
template <typename T> void write(T, char);
template <typename T> T min(T, T);
void AddEdge(int, int);
void dfs(int, int);
void Init();
const int MAXN = 1510;
int n;
int f[MAXN][2];
int main() {
freopen("strategic.in", "r", stdin);
freopen("strategic.out", "w", stdout);
while (scanf("%d", &n) != EOF) {
Init();
for (int i = 1; i <= n; ++i) {
int u = read<int>(), cnt = read<int>();
for (int j = 1; j <= cnt; ++j) {
int v = read<int>();
AddEdge(u + 1, v + 1);
AddEdge(v + 1, u + 1);
}
}
dfs(1, 0);
write(min(f[1][0], f[1][1]), '\n');
// for (int i = 1; i <= n; ++i) {
// fprintf(stderr, "f[%d][0]=%d f[%d][1]=%d\n", i, f[i][0], i, f[i][1]);
// }
}
return 0;
}
struct EDGE {
int v, next;
} edge[MAXN << 1];
int head[MAXN], edgeNum;
void dfs(int now, int fa) {
f[now][0] = 1;
f[now][1] = 0;
for (int i = head[now]; i; i = edge[i].next) {
int v = edge[i].v;
if (v == fa) continue;
dfs(v, now);
f[now][0] += f[v][1];
f[now][1] += f[v][0];
}
}
void AddEdge(int u, int v) {
edge[++edgeNum] = {v, head[u]};
head[u] = edgeNum;
}
void Init() {
memset(edge, 0, sizeof edge);
memset(head, 0, sizeof head);
memset(f, 0, sizeof f);
edgeNum = 0;
}
template <typename T> T min(T x, T y) {
return x < y ? x : y;
}
#define isdigit(ch) (ch >= '0' && ch <= '9')
template <typename T> T read() {
T res = 0, f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return res * f;
}
template <typename T> void write(T x, char ed) {
if (x < 0) x = -x, putchar('-');
static int sta[sizeof(T) << 2], top = 0;
do {
sta[++top] = x % 10;
x /= 10;
} while (x);
while (top) {
putchar(sta[top--] ^ 48);
}
putchar(ed);
}