设想苹果树很象二叉树，每一枝都是生出两个分支。我们用自然数来数这些枝和根那么必须区分不同的枝（结点），假定树根编号都是定为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:输出能保留的苹果数。（剪枝时，千万不要连根拔起哦）。
//============================================================================ // Name : 苹果二叉树new.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #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; }
