蓝桥杯 算法训练 结点选择

题目

问题描述 有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？ 输入格式 第一行包含一个整数 n 。 接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。 接下来一共 n-1 行，每行描述树上的一条边。 输出格式 输出一个整数，代表选出的点的权值和的最大值。 样例输入 5 1 2 3 4 5 1 2 1 3 2 4 2 5 样例输出 12 样例说明 选择3、4、5号点，权值和为 3+4+5 = 12 。 数据规模与约定 对于20%的数据， n <= 20。 对于50%的数据， n <= 1000。 对于100%的数据， n <= 100000。 权值均为不超过1000的正整数。

题目分析

首先，回顾一下 数据结构中 “节点”的定义： 是数据结构中，用来描述“树”型结构的名词。这种结构像一根倒着的树。每片树叶都长在一个结点上，这个结点就叫做这个叶子的父结点，这个叶子叫做父结点的子结点，也叫这棵树的叶结点，它再没有子结点了。 经过对问题的分析，发现，需要用到的思想如下： 1、动态规划的策略进行求解。因为符合$每个阶段的决策，做出的是一组局部的决策结果，而每个阶段都使问题规模变小，且更接近最优解$

---

2、构造树----这是一个树形结构，但不是二叉树（题目中的情况表明可以是多叉数），所以$可以理解为一个图，那么对它的信息进行存储应该用图的存储方式。$对于图的常用存储方式为：邻接矩阵、邻接表。但是，邻接矩阵的存储，是直接分配存储空间，如果输入的数据形成的图（实际上是树，但是也可以理解为图）是稀疏有向图，那么会造成大量内存空间的浪费。所以，采$邻接链表来进行存储$。鉴于题目的信息输入，采取的是 边 的形式输入，且是按照节点的递增顺序，所以采用$链式前向星$进行$边集数组的存储$。

---

3、本题是一个按照图的规则存储的树，根据题目意思，应该深度遍历所输入的树，对它的节点按照 自下而上（从深度最大的地方向着根节点的方向）进行遍历。那么，就需要先进入树的叶节点，所以 动态规划的过程应该是： 回溯算法：先进行递归操作，在递归到可解的最小值（叶节点）处时，逐步返回原问题的解（返回的是局部的决策结果）。 所以，在以图的方式存储数据的时候，应该将边存储为双向边（因为有递归和回溯两个方向要进行）。

---

做一下需要用到的知识的说明

1、动态规划 动态规划的每个阶段的的决策，作出的是一组局部的决策结果。每个阶段都使问题规模变小，且更接近最优解；直到最后一步，问题的规模变为1，就找到问题的最优解，算法结束。那么， 动态规划 = 贪婪策略 + 递推（降阶）+ 存储递推结果 是，全面、分阶段地解决问题。是“带决策的多阶段、多方位的地推算法”。

---

2、构造树----（链式）向前星 建立的边结构体为：

struct Edge { 　 int next; 　 int to; 　 int w; }; 其中edge[i].to表示第i条边的终点, edge[i].next表示与第i条边同起点的上一条边的存位置, edge[i].w为边权值. 另外还有一个数组head[],在加边函数中作用较大。

head[]数组一般初始化为-1,对于加边的add函数是这样的:

cnt = 0；//作为全局变量 void add(int u,int v,int w) { 　 edge[cnt].w = w; 　edge[cnt].to = v; 　edge[cnt].next = head[u];//上一个以cnt作为起点的边的编号 　head[u] = cnt++;//这条边的编号 } 会发现,head[i]保存的是以i为起点的所有边中编号最大的那个,在遍历中可以借这个作为循环的初始值，进行逆序循环（以i为起点的边，从最后生成的那条开始，逐条向前遍历，直至遍历完所有以i为顶点的边）

在遍历以u节点为起始位置的所有边的时候是这样的:

for(int i=head[u]; i!=-1 ;i=edge[i].next) /* 因为数组head[]初始化为-1 edge[cnt].next = head[u];//记录上一个以cnt作为起点的边的编号 所以，只有 以 cnt 为起点的第一条边的上一条边不存在，即，这个时候i=edge[i].next = -1

参考了大佬的博文：原文链接

---

3、动态规划的分析 (状态转移 方程) ： 对于每个点，有两个选择，选和不选。 定义数组 int dp[MAX][2] ; 对于第i个结点， dp[i][0]表示不取该结点，所能达到的最大值 dp[i][0] += max(dp[child][0],dp[child][1]) 不取第i个结点，当前结点所能达到的最大值是，等于i的孩子结点取或者不取所能达到的较大值的和； dp[i][1]表示取该结点，所能达到的最大值 dp[i][1] += dp[child][0] 取第i个结点，当前结点所能达到的最大值是，等于i的每个孩子不取所能达到的最大值的和

---

4、使用深度搜索dfs，自顶向下分解，自底向上回溯求解。

---

5、$本题建立双向边的注意事项：$

int m=0;//定义全局变量 m 的初值为0 // fromnode 是边的起点， tonode是边的终点 int addedge(int fromnode,int tonode) //该树采用链式前向星，并且用双向边的方式，存储边、查找边 { //fromnode指向tonode的边----正向边 edge[m].tonode=tonode;//边指向的节点(边的终点) edge[m].nextedge=head[fromnode];//边的编号--双号 head[fromnode]=m++;//m是全局变量 //tonode指向fromnode的边----反向边 edge[m].tonode=fromnode;//边指向的节点（反向边的终点） edge[m].nextedge=head[tonode];//边的编号--单号 head[tonode]=m++;//m是全局变量 return 0; }

程序源码

具体思路代码中也有注释：

#include<stdio.h> #include<string.h> #define Max 100001 int dp[Max][2];//0代表不选择节点权值；1代表选择节点权值 int head[Max];//存储的是边的顶点的情况--辅助结构体进行存储 int m=0;//计数的全局变量 struct edge { int tonode; int nextedge; } edge[2*Max];//创建结构体，同时定义结构体数组 int addedge(int rootnode,int goalnode) { //构造双向边中的正向边 edge[m].tonode = goalnode; edge[m].nextedge = head[rootnode]; head[rootnode] = m; m++; //构造双向边中的逆向边 edge[m].tonode = rootnode; edge[m].nextedge = head[goalnode]; head[goalnode] = m; m++; //结束 return 0; } int max(int a,int b) { if(a>b) return a; else return b; } int dfs(int goalnode,int rootnode) { int i,n; for(i=head[goalnode];i!=-1;i=edge[i].nextedge) { /* 如果该条边是逆向边，那么结束对起点节点的遍历 **/ if(edge[i].tonode == rootnode) continue; /* 否则，进行递归操作 原来的起点作为新起点的上一节点 **/ n=edge[i].tonode; dfs(n,goalnode); /* 进行动态规划的局部决策 **/ dp[goalnode][0]+=max(dp[n][0],dp[n][1]); dp[goalnode][1]+=dp[n][0]; } return 0; } int main() { int n,s; int i; int rootnode,goalnode;//分别代表边的开始节点、终止节点 memset(dp,0,sizeof(dp)); memset(head,-1,sizeof(head)); scanf("%d",&n); for(i=1;i<=n;i++)//我的数组 从下标为1处开始进行使用 scanf("%d",&dp[i][1]); for(i=1;i<=n-1;i++) { scanf("%d %d",&rootnode,&goalnode); addedge(rootnode,goalnode);//调用函数，进行加边操作 } /* 从根节点开始深度优先遍历 遍历结束，自底向上进行回溯 （假设根节点的父节点为 0） **/ dfs(1,0); /* 最后，还需要对根节点进行判断 因为递归的过程，实际上是从 以根节点为起点的情况进行判断 即，判断除根节点之外的其他情况 所以，最后还需要对根节点进行情况判断 **/ s=max(dp[1][0],dp[1][1]); printf("%d",s); return 0; }

参考原博文