A37451. 活动人数
填空题
困难
知识点
题目描述
活动人数
题目描述：
有一个大型企业集团，由N个部门组成，编号从1到N。这些部门之间的层次关系形成了一个树状结构，一个上级部门可能会有1个或多个直接下级部门，一个下级部门只有一个直接上级部门。
本月集团举办了一个大型活动，这次的活动组织方按如下要求安排活动：
1. 来的人越多越好；
2. 如果一个上级部门参加本次活动，那么他们的直接下级部门就不能参加，而他的间接下集部门可以参加（如下图，如果部门1参加，那么部门2、3不能参加，而部门4、5、6可以参加）。
请你帮他们计算一下，如何安排可以使参加活动的人数最多，并输出参加活动的最多人数。
例如：当N=6，每个部门编号为1到6，部门上下级关系和部门的人数如下图所示：
注意：示例中，部门1是层级最高的部门，没有直接上级，故将其直接上级部门设为0；
当安排（1、4、5、6）这4个部门参加活动时，人数最多，为11，所以输出11。
输入描述
第一行输入一个正整数N（1≤N≤100000），表示集团所有部门的数量
接下来有N行，每行输入三个非负整数F、S和C，（0≤F≤N，1≤S≤N，F≠S，1≤C≤1000），F表示是部门S的直接上级，C表示部门S的人数，整数之间用一个空格隔开
注意：如果是最上层的部门，其直接上级部门编号为0
输出描述
输出一个整数，表示参加活动的最多人数
样例输入
6
0 1 2
1 2 4
1 3 3
2 4 3
3 5 2
3 6 4
样例输出
11
参考答案
//树图+深搜+动规
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, root;//n储存所有部门的数量 root储存根节点
int a[N];// a数组表示每个节点的权值
int f[N][2]; // f[i][0/1]表示不选/选i节点时的最大价值
vector<int> G[N]; // 存储树的图结构
void dfs(int u){
f[u][1] = a[u]; // 初始化选u节点的最大价值为它本身的权值
for (int v : G[u]){//相当于for(int v=0;v<G[u].size();v++)
dfs(v); // 遍历v节点
f[u][1] += f[v][0]; // 如果选择了u节点，则不能选择v节点，所以累加 f[v][0]
f[u][0] += max(f[v][0],f[v][1]); // 如果不选择u节点，则可以选择v节点
// 所以取 f[v][0] 和 f[v][1] 的较大值累加起来
}
}
int main()
{
cin >> n;
for (int i = 1, f, s; i <= n; i++){
cin >> f >> s >> a[s]; // 输入父节点、子节点和子节点权值
if (f) G[f].push_back(s); // 如果有父亲节点则建立G[f] -> [s]的边
else root = s; // 否则当前节点为根节点
}
dfs(root);
cout << max(f[root][0],f[root][1]);
return 0;
}
上一题
下一题