首页 > 代码库 > 蓝桥杯 节点选择 树状动态规划
蓝桥杯 节点选择 树状动态规划
算法训练 结点选择
时间限制:1.0s 内存限制:256.0MB
锦囊1
使用树型动态规划。
锦囊2
用F[i]表示从子树i中选择结点,且结点i必须被选择的最大值,用G[i]表示从子树i中选择结点,且结点i必须不被选择的最大值。
则F[i]=a[i]+\sum(G[j]),其中a[i]表示结点i的权值,j是i的子结点。
G[i]=\sum(max(F[j], G[j])),其中j是i的子结点。
问题描述
有一棵 n 个节点的树,树上每个节点都有一个正整数权值。如果一个点被选择了,那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少?
输入格式
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数,第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行,每行描述树上的一条边。
输出格式
输出一个整数,代表选出的点的权值和的最大值。
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 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的正整数。
/************************************************************************* > File Name: selectPoint.c > Author: litingdong > Mail: litingdong2012@gmail.com > Created Time: 2014年05月18日 星期日 19时39分55秒 ************************************************************************/ #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 100000 #define max(x,y) ((x)>(y)?(x):(y)) int head[N+1]; int val[N+1]; int vis[N+1]; struct EDGE { int to,next; }edge[N*2]; struct NODE { int yes,no;//yes代表选择根节点,no代表不选择根节点,从子节点中选取 }node[N]; int m=0; void add_edge(int u,int v) { edge[m].to=v; edge[m].next=head[u]; head[u]=m++; } void maxValue(int x)//类似于深度优先遍历 { vis[x]=1; int i; node[x].yes=val[x]; node[x].no=0; for(i=head[x];i!=-1;i=edge[i].next) { int v=edge[i].to; if(vis[v]) continue; maxValue(v); node[x].yes+=node[v].no;//选择了父节点,则子节点不能再选了 node[x].no+=max(node[v].yes,node[v].no);//如果父节点没有选择,则子节点可以选,也可以不选,从这两种情况中选择一个最优值. } } int main() { //freopen("input1.txt","r",stdin); int n; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(head)); scanf("%d",&n); int i; for(i=1;i<=n;i++) scanf("%d",&val[i]); int a,b; for(i=0;i<n-1;i++) { scanf("%d%d",&a,&b); add_edge(a,b); add_edge(b,a); } maxValue(1); printf("%d\n",max(node[1].yes,node[1].no)); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。