首页 > > 程序设计 > C/C++ >

P2015 二叉苹果树

2018-06-17 22:26:45来源：未知阅读 ()

题目描述

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）

这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

输入输出格式

输入格式：

第1行2个数，N和Q(1<=Q<= N,1<N<=100)。

N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

这是一道比较不错的树形DP的题目，
刚开始的时候用贪心乱搞，搞了搞边，搞了搞点，搞了颗树，搞了39分。。。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 const int MAXN=1001;
  7 int n,q;
  8 int v[MAXN];
  9 int vis[MAXN];
 10 int deep[MAXN];
 11 int read(int & n)
 12 {
 13     char p='+';int x=0;
 14     while(p<'0'||p>'9')
 15         p=getchar();
 16     while(p>='0'&&p<='9')
 17     x=x*10+p-48,p=getchar();
 18     n=x;
 19 }
 20 struct node
 21 {
 22     int u;
 23     int v;
 24     int w;
 25     int nxt;
 26 }edge[MAXN];
 27 int num=1;
 28 int head[MAXN];
 29 void add_edge(int x,int y,int z)
 30 {
 31     edge[num].u=x;
 32     edge[num].v=y;
 33     edge[num].w=z;
 34     edge[num].nxt=head[x];
 35     head[x]=num++;
 36 }
 37 struct deal
 38 {
 39     int how;
 40     int val;
 41     int l;
 42 }a[MAXN];
 43 void build_tree(int p)
 44 {
 45     vis[p]=1; 
 46     for(int i=head[p];i!=-1;i=edge[i].nxt)
 47     {
 48         if(vis[edge[i].v]==0)
 49         {
 50             deep[edge[i].v]=deep[p]+1;
 51             build_tree(edge[i].v);
 52         }
 53         
 54     }
 55 }
 56 void deal_val(int p,int pre)
 57 {
 58     vis[p]=1;
 59     for(int i=head[p];i!=-1;i=edge[i].nxt)
 60     {
 61         int will=edge[i].v;
 62         if(will!=0&&vis[will]==0&&deep[will]>deep[p])
 63         {
 64             a[pre].l++;
 65             a[pre].val+=edge[i].w;
 66             deal_val(will,pre);
 67         }
 68         
 69         
 70     }
 71 }
 72 int comp(const deal & a ,const deal & b)
 73 {
 74     if(a.val!=b.val)
 75     return a.val<b.val;
 76     return edge[head[a.how]].w<edge[head[b.how]].w;
 77 }
 78 int main()
 79 {
 80     int ans=0;
 81     read(n);read(q);
 82     q=n-q;
 83     for(int i=1;i<=n;i++)
 84         head[i]=-1,a[i].how=i;
 85     for(int i=1;i<=n-1;i++)
 86     {
 87         int x,y,z;
 88         read(x);read(y);read(z);
 89         ans=ans+z;
 90         add_edge(x,y,z);
 91         add_edge(y,x,z);
 92     }
 93     deep[1]=1;
 94     build_tree(1);
 95     for(int i=1;i<=n;i++)
 96     {
 97         memset(vis,0,sizeof(vis));
 98         deal_val(i,i);
 99     }
100         
101     sort(a+1,a+n+1,comp);
102     
103     for(int i=1;i<=q-1;i++)
104         ans=ans-edge[head[a[i].how]].w;    
105     cout<<ans;
106     return 0;
107 }

贪心

后来看题解用树形DP，

对于每一个节点，我们可以枚举它相连的边，

用dp[i][j]表示第i个节点，在他的子节点中保留j条树枝的最大值

那么我们可以枚举节点和j，当然，在枚举j的时候我们需要同时枚举一个k

我们可以想一下，该节点i需要保留j条边，那么我们取他的最大值得时候，可以对他相连的节点进行DP，

如果j=5，这时候需要保留5条边，

因为整个树是二叉树，所以说，他的相连的一条边所能删除的最大数就是4（相连的线段一定会删除）

那么k的范围：0--4

动态转移方程：

dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[will][k]+edge[i].w);

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1001;
 7 int n,q;
 8 int v[MAXN];
 9 int vis[MAXN];
10 int deep[MAXN];
11 int dp[MAXN][MAXN];
12 int read(int & n)
13 {
14     char p='+';int x=0;
15     while(p<'0'||p>'9')
16         p=getchar();
17     while(p>='0'&&p<='9')
18     x=x*10+p-48,p=getchar();
19     n=x;
20 }
21 struct node
22 {
23     int u;
24     int v;
25     int w;
26     int nxt;
27 }edge[MAXN];
28 int num=1;
29 int head[MAXN];
30 void add_edge(int x,int y,int z)
31 {
32     edge[num].u=x;
33     edge[num].v=y;
34     edge[num].w=z;
35     edge[num].nxt=head[x];
36     head[x]=num++;
37 }
38 int dfs(int u,int fa)
39 {
40     int ans=0;
41     for(int i=head[u];i!=-1;i=edge[i].nxt)
42     {
43         int will=edge[i].v;
44         if(will==fa)
45             continue;
46         ans+=dfs(will,u)+1;
47         for(int j=min(q,ans);j>=1;j--)
48         {
49             for(int k=min(j,ans)-1;k>=0;k--)
50             {
51                 dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[will][k]+edge[i].w);
52             }
53         }
54     }
55     return ans; 
56 }
57 int main()
58 {
59     read(n);read(q);
60     for(int i=1;i<=n;i++)
61         head[i]=-1;
62     for(int i=1;i<=n-1;i++)
63     {
64         int x,y,z;
65         read(x);read(y);read(z);
66         add_edge(x,y,z);
67         add_edge(y,x,z);
68     }
69     dfs(1,0);
70     cout<<dp[1][q];
71     return 0;
72 }