ALGO-4_蓝桥杯_算法训练_结点选择

2018/02/24 21:48
阅读数 14
问题描述
有一棵 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.使用转移方程,从而满足题目要求(如果一个点被选择了,那么在树上和它相邻的点都不能被选择.)

转移方程为:

dp[u][1]+=dp[v][0];//选择了u结点,则与它邻接的结点不选;

dp[u][0]+=max(dp[v][0],dp[v][1]);不选择u结点,则与它邻接的结点选择结果最大的;

 相关链接:http://blog.csdn.net/buctyyzyn/article/details/43484991

 


2.存储数据时,使用解链式向前星结构(邻接表);

  以题目为例,分析解链式向前星结构

  (皆为双向箭头)

  1->输入的顺序依次为:

  1 2

  1 3

  2 4

  2 5

  

  2->按照图以及输入模拟:

  

  从而实现深度优先搜索.

 相关链接:http://blog.csdn.net/acdreamers/article/details/16902023

 

疑问:用C提交代码会出现超时现象?

 

示例代码:

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAX(x,y) (x)>(y)?(x):(y)
 5 #define Max_ 10010
 6 
 7 int M = 0;
 8 int dp[Max_][2];    
 9 int head[Max_];
10 
11 struct edge{
12   int to;    /*记录子节点的权值*/
13   int next;    /*记录当前节点的另一个子节点的索引*/ 
14 }e[Max_*2];
15 
16 void add(int from,int to)
17 {
18   e[M].to = to;    
19   e[M].next = head[from];    
20   head[from] = M++;
21   return ;
22 }
23 
24 void dfs(int x, int pre)
25 {
26   int i = 0 , k = 0 ;
27   for (i = head[x] ; i != -1 ; i = e[i].next)
28   {
29     k = e[i].to;
30     if (k == pre)    
31     {
32       continue;    /*即当前节点无子节点*/ 
33     }
34     dfs(k,x);    /*k->当前节点 , x->父节点*/
35     dp[x][0] += MAX(dp[k][0],dp[k][1]);
36     dp[x][1] += dp[k][0];
37   }
38   return ;
39 }
40 
41 int main(void)
42 {
43   int n = 0 , i = 0 , from = 0 , to = 0 ;
44   
45   /*节点数*/
46   scanf("%d",&n);
47   memset(head,-1,sizeof(head));
48   memset(dp,0,sizeof(dp));
49 
50   /*各节点权值*/ 
51   for (i = 1 ; i <= n ; i ++)
52   {
53     scanf("%d",&dp[i][1]);
54   }
55 
56   /*节点间的连接*/
57   for (i = 1 ; i <= n-1 ; i ++)
58   {
59     scanf("%d %d",&from,&to);
60     add(from,to);
61     add(to,from);
62   }
63 
64   dfs(1,-1);
65   printf("%d",MAX(dp[1][1],dp[1][0]));
66   return 0;
67 }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部