题目描述
有一棵苹果树,如果树枝有分叉,一定是分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
思路:题意就是给你n-1条树枝,每条树枝上都带有一定的苹果,问最后留下m根树枝,能拥有的苹果的最大值,根节点为1,每个节点只有2种情况,有2个儿子,或没有儿子。 这题是一个很典型的树形结构,因为节点以边相连,又为二叉结构,无环。我们这时候从根节点下顺,找到最深的儿子,然后一步步开始回溯,以当前回溯到的这个点作为根,考虑他有几条边的最大值。那从下至上递推回去,根节点的状态只与2个子节点有关,很明显,这就是一个dp,且是树形的。
这道题先列出状态转移方程:dp[i][j]=max(dp[i][j],dp[i][i-j-1]+dp[son[i]][k]+val[i][son[i]])。之后推导一下过程就可以了。
AC代码:
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
const int maxx=1000;
using namespace std;
vector<int>son[maxx];
int dp[maxx][maxx];
int vis[maxx];
int val[maxx][maxx];
int n,m;
void dfs(int x)
{
int slen=son[x].size();
vis[x]=1;//经过的点进行标记,不再处理
for(int i=0;i<slen;i++)
{
int y=son[x][i];
if(vis[y]==1)
continue;
vis[y]=1;
dfs(y);
for(int j=m;j>=1;j--)
{
for(int k=j-1;k>=0;k--)
{
dp[x][j]=max(dp[x][j],dp[x][j-k-1]+dp[y][k]+val[x][y]);
}
}
}
}
int main()
{
cin>>n>>m;
int u,v,w;
for(int i=1;i<n;i++)
{
cin>>u>>v>>w;
son[u].push_back(v);
son[v].push_back(u);//建双向边,不知道哪个是儿子,哪个是父亲
val[u][v]=w;
val[v][u]=w;//赋值给边
}
dfs(1);//从根节点开始
cout<<dp[1][m]<<endl;//回溯至最开始的根节点,m条边的最大值
return 0;
}