极限简单题:
二叉苹果树(apple)
Ural 1018
【问题描述】
有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点)。这棵树共有N个结点(叶子点或者树枝分叉点),编号为1~~N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树
现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量,求出最多能留住多少苹果。
不得不说出题人真是好人
题目最重要一个条件:
二叉!
二叉!!
二叉!!!(重要的事情说三遍)
真为我们省事
1为苹果树的根
2,3,4..就是它的叉
一条边连接的一个父亲和一个儿子
这里我们存为x和y
#include <cstdio>
#include <cstring>
using namespace std;
struct node
{
int x,y,d,next;
//x:这条边所连接的父亲
//y:这条边所连接的儿子
//d:这个叉上长了多少个苹果
//next:上一条边的编号
}a[];
int last[],n,k,len=;
//last[len]:len这个点最后一条和它相连的边的编号
struct nodetr
{
int l,r;
nodetr()
{
l=;r=;
}
}tr[];
int f[][];
bool bk[];
void ins(int x,int y,int c)//建边
{
len++;
a[len].x=x;a[len].y=y;a[len].d=c;
a[len].next=last[x];last[x]=len;
}
int mymax(int x,int y)
{
return x>y?x:y;
}
void dfs(int x)//这里用了多叉树的方法来做得
{
for (int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if (bk[y]==true)
{
bk[y]=false;
f[y][]=a[k].d;
if (tr[x].l==) tr[x].l=y;
else tr[x].r=y;
dfs(y);
}
}
}
int treedp(int x,int kk)//DP
{
//f[i][j]:i:到哪一个点惹;j:保留多少个点
if (f[x][kk]!=-) return f[x][kk];//如果已经做过就直接输出
int maxx=;
for (int i=;i<=kk-;i++)
{
int ll,rr,trl,trr;
ll=i;
rr=kk--i;
//分为左右两部分,分别保留ll个枝和rr个枝
trl=treedp(tr[x].l,ll);
trr=treedp(tr[x].r,rr);
//分别DP一遍
maxx=mymax(trl+trr+f[x][],maxx);
}
f[x][kk]=maxx;
return maxx;
}
int main()
{
scanf("%d%d",&n,&k);
memset(last,,sizeof(last));
int x,y,c;
for (int i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);
ins(y,x,c);
}
memset(f,-,sizeof(f));
memset(bk,true,sizeof(bk));
bk[]=false;
dfs();
for (int i=;i<=n;i++) f[i][]=;
f[][]=;
printf("%d\n",treedp(,k+));
return ;
}