有一棵苹果树,如果树枝有分叉,一定是分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:
5 2
1 3 1
1 4 10
2 3 20
3 5 20
输出样例#1:
21
这是一道比较不错的树形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 }