1 条题解
-
0陈烨鑫 (chenyexin) LV 10 @ 2023-4-25 20:04:03
是有些难度 AC代码:
#include<iostream> #include<cstring> using namespace std; const int N = 1510; int h[N], e[N], ne[N], idx; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } int n, m; int f[N][2]; bool vis[N]; void dfs(int u) { f[u][0] = 0, f[u][1] = 1; //初始化 for(int i = h[u]; i != -1; i = ne[i]){ int j = e[i]; dfs(j); f[u][0] += f[j][1]; //当前节点不选 f[u][1] += min(f[j][0], f[j][1]);//选当前节点 } } int main() { while(cin >> n){ int a, b; memset(vis, false, sizeof vis); idx = 0; memset(h, -1, sizeof h); for(int i = 0; i < n; i++){ scanf("%d:(%d)", &a, &m); while(m--){ cin >> b; vis[b] = true; add(a, b); } } int root = 0; while(vis[root])root++; //寻找一个根节点 dfs(root); cout << min(f[root][0], f[root][1]) << endl; //输出俩种情况的最小值 } return 0; }
- 1
信息
- ID
- 233
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 65
- 已通过
- 18
- 上传者