2806 - 二叉苹果树
时间限制 : 1 秒
内存限制 : 128 MB
有一棵苹果树，如果树枝有分叉，一定是分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
C语言解答
#include <stdio.h> #include <stdlib.h> #include <math.h> int n, q; struct ben { int to, last, val, dq; }a[205]; int f[205][205]; int cnt = 1; int head[205]; void add(int x, int y, int num) { a[cnt].to = y; a[cnt].last = head[x]; a[cnt].dq = x; a[cnt].val = num; head[x]=cnt++; } void search(int dq, int fa) { for(int i = head[dq];i >0; i = a[i].last) { int b = a[i].to; if(b == fa)continue; f[b][1]=a[i].val; search(b,dq); for(int j = q;j >= 1; j--) { for(int k = 0;k <= j; k++) { if((j != 1 && j != k) || dq == 1) { f[dq][j] = fmax(f[dq][j],f[b][k]+f[dq][j-k]); } } } } } int main() { scanf("%d%d",&n,&q); for(int i = 1;i <= n; i++) { head[i]=-1; } for(int i = 1;i < n; i++) { int x, y, num; scanf("%d%d%d",&x,&y,&num); add(x,y,num); add(y,x,num); } search(1,0); printf("%d\n",f[1][q]); return 0; }
C++解答
#include<iostream> #include<cstring> #include<cstdio> using namespace std; struct tree { int lc,rc,data; }; const int maxn=101; int n,q,a[maxn][maxn],f[maxn][maxn]; bool flag[maxn]={0}; tree t[maxn]; void init(); void buildtree(int); int dp(int,int); int main() { //freopen("apple11.in","r",stdin); init(); buildtree(1); cout<<dp(1,q)<<endl; return 0; } void init() { cin>>n>>q; q++;//q条树枝需要q+1个点 memset(t,0,sizeof(t)); memset(a,-1,sizeof(a));//有些树枝可能没有苹果 memset(f,-1,sizeof(f));// memset(flag,0,sizeof(flag)); for(int i=1;i<n;i++) { int x,y,z; cin>>x>>y>>z; a[x][y]=a[y][x]=z; } } void buildtree(int x) { flag[x]=true;//当前点进树 for(int i=1;i<=n;i++) { if(!flag[i] && a[x][i]!=-1)//找和x点直接相连且不在树上的点 { if(t[x].lc==0) t[x].lc=i;//如果x没有坐子树，则i为其左儿子 else t[x].rc=i;//如果有左儿子则为其右儿子，因为和x相连的点只有2个或者没有 t[i].data=a[x][i];//i点的值域记录的是i到其父亲节点的苹果数 buildtree(i);//对i点递归建树 } } } int dp(int x,int y)//表示以下x为根，保留y个节点 { if(f[x][y]!=-1)return f[x][y];//如果f[x][y]有值则不用再计算 if(x==0||y==0) { f[x][y]=0;//x=0表示该节点没有子树，是叶节点，y=0表示没有节点 return f[x][y]; } f[x][y]=0; for(int i=0;i<=y-1;i++) { int ls=dp(t[x].lc,i);//x的左儿子为根，保留i个节点 int rs=dp(t[x].rc,y-1-i);//x的右儿子为根，保留y-1-i个节点，因为x节点必须保留，所以y-1 if(f[x][y]<ls+rs) f[x][y]=ls+rs; } f[x][y]+=t[x].data; return f[x][y]; }