二叉苹果树

描述

有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点)。
这棵树共有N个结点(叶子点或者树枝分叉点),编号为1-N,树根编号一定是1。
    我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝
的树:
    2    5
    \  /
       3       4
       \  /
         1

 

现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量,求出最多能留住多少苹果。注意树根不能剪没了哟。

输入

第1行2个数,N和Q(1<=Q<=N,I<N<=IOO)。
N表示树的结点数,Q表示要保留的树枝数量。
接下来N-I行描述树枝的信息。 每行3个整数,前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。 每根树枝上的苹果不超过30000个。

输出

一个数,最多能留住的苹果的数量。

样例

输入

5 2
1 3 1
1 4 10
3 2 20
3 5 20 

输出

21
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,head[10001],tot,f[1001][1001],q,root=1,edge[10001],use[10001];
 4 struct data {
 5     int to,nxt,val;
 6 } e[10001];
 7 void build(int x,int y,int z) {
 8     e[++tot].to=y;
 9     e[tot].val=z;
10     e[tot].nxt=head[x];
11     head[x]=tot;
12 }
13 void dp(int x) {
14     use[x]=1;
15     for(int i=head[x]; i; i=e[i].nxt) {
16         int v=e[i].to;
17         if(use[v])
18             continue;
19         dp(v);
20         edge[x]+=edge[v]+1;
21         for(int p=min(q,edge[x]); p>=1; p--)
22             for(int k=min(edge[v],p-1); k>=0; k--)
23                 f[x][p]=max(f[x][p-k-1]+e[i].val+f[v][k],f[x][p]);
24     }
25 }
26 int main() {
27     scanf("%d%d",&n,&q);
28     for(int i=1; i<=n-1; i++) {
29         int x,y,z;
30         scanf("%d%d%d",&x,&y,&z);
31         build(x,y,z);
32         build(y,x,z);
33     }
34     dp(root);
35     printf("%d\n",f[root][q]);
36     return 0;
37 }

 

二叉苹果树

上一篇:Caused by: org.yaml.snakeyaml.parser.ParserException: while parsing a block mapping


下一篇:推荐几个移动端前端UI框架