题目描述
有一棵苹果树,如果树枝有分叉,一定是分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个。
输出格式
一个数,最多能留住的苹果的数量。
输入输出样例
输入
5 2
1 3 1
1 4 10
2 3 20
3 5 20
输出
21
思路
先用邻接矩阵和递归建树,
t
r
e
e
[
x
]
[
1
]
tree[x][1]
tree[x][1]表示节点x的左节点,
t
r
e
e
[
x
]
[
1
]
tree[x][1]
tree[x][1]表示它的右节点。
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示以第i个节点为根,保留j条树枝的最多苹果,
n
u
m
[
i
]
num[i]
num[i]表示子节点为
i
i
i的边的权值。
d
f
s
dfs
dfs序枚举
i
i
i,再枚举
k
k
k,
0
<
=
k
<
j
0<=k<j
0<=k<j,得:
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
]
,
(
f
[
t
r
e
e
[
i
]
[
1
]
]
[
k
]
+
f
[
t
r
e
e
[
i
]
[
2
]
]
[
j
−
k
−
1
]
+
n
u
m
[
i
]
)
)
f[i][j]=max(f[i][j],(f[tree[i][1]][k]+f[tree[i][2]][j-k-1]+num[i]))
f[i][j]=max(f[i][j],(f[tree[i][1]][k]+f[tree[i][2]][j−k−1]+num[i]))
代码
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
int n,q,f[101][101],x,y,a,m[101][101],e[101],tree[101][3];
void in()
{
cin>>n>>q;
for(int i=1;i<=100;i++) for(int j=1;j<=100;j++) m[i][j]=-1;//初始化不可少
for(int i=1; i<n; i++)
{
cin>>x>>y>>a;
m[x][y]=m[y][x]=a;//邻接矩阵
}
}
void build(int x)//递归建树
{
int t=1;
for(int i=1; i<=100; i++)
{
if(m[x][i]>=0)
{
e[i]=m[x][i];
m[x][i]=m[i][x]=-1;
tree[x][t++]=i;
build(i);
if(t>2) break;
}
}
}
void tdp(int x,int k)
{
if(!k) return;
int l=tree[x][1],r=tree[x][2];
if(!l) f[x][k]=e[x];
else
{
f[x][k]=e[x];
for(int i=0; i<k; i++)
{
if(!f[l][i]) tdp(l,i);
if(!f[r][k-i-1]) tdp(r,k-i-1);
f[x][k]=max(f[x][k],(f[l][i]+f[r][k-i-1]+e[x]));//状态转移
}
}
}
int main()
{
in();
build(1);
tdp(1,q+1);
cout<<f[1][q+1];
}