_Faith_ @ 2022-08-11 17:30:22
#include<bits/stdc++.h>
using namespace std;
int ver[2010], hd[1010], idx, nxt[2020], dp[101][2];
int n;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void add(int x, int y) {
ver[++idx] = y;
nxt[idx] = hd[x];
hd[x] = idx;
}
inline void dfs(int x, int y) {
dp[x][1] = 1;
dp[x][0] = 0;
for (int i = hd[x]; i; i = nxt[i]) {
if (ver[i] == y)
continue;
dfs(ver[i], x);
dp[x][0] += dp[ver[i]][1];
dp[x][1] += min(dp[ver[i]][1], dp[ver[i]][0]);
}
}
int main() {
n = read();
for (int i = 1; i <= n; i++) {
int x = read() + 1;
int k = read();
for (int j = 1; j <= k; j++) {
int y = read() + 1;
add(x, y);
add(y, x);
}
}
dfs(1, 0);
cout << min(dp[1][0], dp[1][1]);
return 0;
}
by W9W9 @ 2022-08-11 17:52:13
hd开小了
by ssxvngn @ 2022-08-11 17:57:01
@Faith int ver[3010], hd[1510], idx, nxt[3020], dp[1510][2];
就可以了。
by _Faith_ @ 2022-08-11 17:59:00
谢谢大佬们,AC啦,orz