题面
Description
有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点)这棵树共有N个结点(叶子点或者树枝分叉点),编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量,求出最多能留住多少苹果。下面是一颗有 4 个树枝的树。
2 5
\ /
3 4
\ /
1
Input
第1行2个数,N和Q(1<=Q<= N,1<N<=100)。N表示树的结点数,Q表示要保留的树枝数量。
接下来N-1行描述树枝的信息,每行3个整数,前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。
Output
剩余苹果的最大数量。
Sample Input
5 2
1 3 1
1 4 10
2 3 20
3 5 20
Sample Output
21
题解
这道题很久,很久,很久以前,我是会做的
但是,今天,我再看,我这个小蒟蒻因为太垃圾了,所以不会做了。(迷茫)
于是,我决定很详细的写一写
首先定义状态
f[i][j]表示,以i为根节点,剩余j根树枝的时候的最大苹果树
那么状态的转移我们可以考虑一下
对于当前的f[i][j]而言,
f[i][j]=max{f[son][j-k]+f[i][k-1]+w[edge]}
其中w是边权,son是子节点
为什么?
对于一棵子树,当其保留j根枝条的时候
显然两棵子树可以分别保留 k-1,j-k 根枝条
因此,就有了上面的公式
好了,接下来就是代码。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 200
int f[MAX][MAX];
int n,q;
vector<int> e[MAX],w[MAX];
//f[i][j]表示以i为根节点的子树,剩余j根枝条时,剩余的最大苹果数
int build(int u,int ff)//建树,并求解
{
int son=0;
for(int i=0;i<e[u].size();++i)
{
int v=e[u][i];
if(v==ff)continue;
son+=build(v,u)+1;//统计子节点
for(int j=min(son,q);j;--j)
for(int k=min(j,q);k;--k)
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k-1]+w[u][i]);
}
return son;
}
int main()
{
cin>>n>>q;
int u,v,x;
for(int i=1;i<n;++i)
{
cin>>u>>v>>x;
e[u].push_back(v);
e[v].push_back(u);
w[u].push_back(x);
w[v].push_back(x);
//tot+=c;
}
build(1,1);
cout<<f[1][q]<<endl;
return 0;
}