设想苹果树很象二叉树,每一枝都是生出两个分支。我们用自然数来数这些枝和根那么必须区分不同的枝(结点),假定树根编号都是定为1,并且所用的自然数为1到N。N为所有根和枝的总数。例如下图的N为5,它是有4条枝的树。
2 5
/ /
3 4
/ /
1
当一棵树太多枝条时,采摘苹果是不方便的,这就是为什么有些枝要剪掉的原因。现在我们关心的是,剪枝时,如何令到损
失的苹果最少。给定苹果树上每条枝的苹果数目,及必须保留的树枝的数目。你的任务是计算剪枝后,能保留多少苹果。
input:
首行为N,Q (1 <= Q <= N, 1 < N <= 100), N为一棵树上的根和枝的编号总数,Q为要保留的树枝的数目。以下N-1行
为每条树枝的描述,用3个空格隔开的整数表示,前2个数为树枝两端的编号,第三个数为该枝上的苹果数。假设每条枝上的苹
果数不超过3000个。
output:
输出能保留的苹果数。(剪枝时,千万不要连根拔起哦)。
#include <iostream>
using namespace std;
int N,Q;
int a[100][100];
int f[100][100];
void init_f()
{
N=5;
Q=2;
for(int i=0;i<=N;i++)
{
for(int j=0;j<=N;j++)
{
f[i][j]=0;
a[i][j]=0;
}
}
a[1][3]=1;
a[1][4]=10;
a[2][3]=20;
a[3][5]=20;
a[3][1]=1;
a[4][1]=10;
a[3][2]=20;
a[5][3]=20;
}
void find_left_right(int root ,int &left,int &right)
{
left=0;
right=0;
for(int i=1;i<=N;i++)
{
if(a[i][root]&&a[root][i]&&a[i][root]==a[root][i])
{
left=i;
}
}
for(int i=1;i<=N;i++)
{
if(a[i][root]&&a[root][i]&&a[i][root]==a[root][i]&&i!=left)
{
right=i;
}
}
}
int compute_f(int root,int number)
{
if(root<=0)
{
f[root][number]=0;
return 0;
}
if(number<=0)
{
f[root][number]=0;
return 0;
}
int left,right;
find_left_right( root ,left,right);
if(left>0&&number>0)
{
int number1=compute_f(left,number-1)+a[root][left];
if(f[root][number]<number1)
f[root][number]=number1;
}
if(right>0&&number>0)
{
int number2=compute_f(right,number-1)+a[root][right];
if(f[root][number]<number2)
f[root][number]=number2;
}
if(right>0&&left>0&&number>0)
{
for(int i=1;i<=number-2;i++)
{
int number1=compute_f(left,i)+a[root][left];
int number2=compute_f(right,number-2-i)+a[root][right];
if(f[root][number]<number2+number1)
f[root][number]=number2+number1;
}
}
cout<<"f["<<root<<"]["<<number<<"]="<<f[root][number]<<endl;
return f[root][number];
}
int main() {
init_f();
compute_f(1,Q); //root is 1;
cout <<f[1][Q]<<endl;
return 0;
}