1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int N=1600; vector<int> G[N]; int f[N][2][2]; /* 这里的 安全 表示以x为根的子树全部都安全 不安全 表示以x为根的子树除了x都安全 f[x][0][0]表示 x这个点 不安全,不派人, f[x][0][1]表示 x这个点 不安全, 派人, ———很明显不合理所以去除 f[x][1][0]表示 x这个点 安全,不派人, f[x][1][1]表示 x这个点 安全, 派人, */ void dp(int x, int fa) { f[x][1][1] = 1; f[x][1][0] = 0; for(int y : G[x]) if(y != fa) { dp(y, x); f[x][1][0] += f[y][1][1]; f[x][1][1] += min(f[y][1][0], f[y][1][1]); } } int main() { int n; while(scanf("%d", &n) != EOF) { memset(G, 0, sizeof(G)); for(int i=1, x, m; i <= n; i++) { scanf("%d:(%d)", &x, &m); for(int j=1, y; j <= m; j++) { scanf("%d", &y); G[x].emplace_back(y); G[y].emplace_back(x); } } int rt = 1; dp(rt, -1); printf("%d\n", min(f[rt][1][0], f[rt][1][1])); } return 0; }
- 1
信息
- ID
- 304
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 290
- 已通过
- 34
- 上传者