第十四届蓝桥杯省赛C++编程题解;活动人数

2023-05-18 09:20:12    动态资讯   

活动人数有一个大型企业集团,由N个部门组成,编号从1N。这些部门之间的层次关系形成了一个树状结构,一个上级部门可能会有1个或多人直接下级部门,一个下级部门只有一个直接上级部门。

本月集团举办了一个大型活动,这次的活动组织方按如下要求安排活动:

1.来的人越多越好

2.如果一个上级部门参加本次活动,那么他们的直接下级部门就不能参加,而他的间接下集部门可以参加 (如下图,如果部门1参加,那么部门23不能参加,而部门456可以参加)

请你帮他们计算一下,如何安排可以使参加活动的人数最多,并输出参加活动的最多人数。例如N=6,每个部门编号为16,部门上下级关系和部门的人数如图所示:

注意示例中,部门1是层级最高的部门,没有直接上级,故将其直接上级部门设为0;当安排 (1456) 4人部门参加活动时,人数最多,为11,所以输出11

 

【输入描述】

第一行输入一个正整数N (1<n<100000),表示集团所有部门的数量接下来有N行,每行输入三个非负整数FSC, (0FN1SNFS1C1000) 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<iostream>
#include<vector>
using namespace std;
int n,x,y,z,root;
int val[100005];//val[i]存储了第i个部门的人数 
int f[100005][2];
//f[i][0]为第i个部门不参加活动的最优解 
//f[i][1]为第i个部门参加活动的最优解 
vector<int> a[100005];//邻接表,a[i][j]表示以i为上级部门的第j个子部门的编号 
 
void dfs(int p)
{
  f[p][0]=0;//如果部门p不参加,则其初始值为0 
  f[p][1]=val[p];//如果部门p参加,其初始值为val[p] 
  for(int i=0;i<a[p].size();i++)//检查部门p的所有下级部门 
  {
    dfs(a[p][i]);//计算出下级部门的最优解 
    f[p][1]+=f[a[p][i]][0];//如果部门p参加,则下级所有部门都不参加 
    f[p][0]+=max(f[a[p][i]][0],f[a[p][i]][1]);//如果部门p不参加,则下级所有部门可参加可不参加 
  }
}
 
int main() 
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++) 
  {
    scanf("%d%d%d",&x,&y,&z);
    if(x==0)root=y;//记录根结点的位置 
    a[x].push_back(y);
    val[y]=z;
  }
  dfs(root);//根不一定是第1个
  printf("%d",max(f[1][0],f[1][1]));
  return 0;
}