【♂Not The Triumph♂O(∩_∩)O哈哈~But The Struggle♂】

竞赛决不是捷径,它只是另一种艰辛的生活方式。得到与失去,只有时间会去评判;成功与失败,只有历史能去仲裁。我不会永远成功,正如我不会永远失败一样

  C++博客 :: 首页 :: 联系 ::  :: 管理
  6 Posts :: 239 Stories :: 25 Comments :: 0 Trackbacks

常用链接

留言簿(7)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 104232
  • 排名 - 233

最新评论

阅读排行榜

评论排行榜

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


【参考程序】:
#include<cstring>
#include
<cstdio>
#include
<iostream>
using namespace std;

struct node
{
    
int lc,rc;
    
int s;
} tree[
220];
int F[110][110],apple[110][110];
bool vis[110];
int n,q;
void make_tree(int root)
{
    vis[root]
=true;
    
for (int i=1;i<=n;i++)
        
if (!vis[i] && apple[root][i]!=-1)
        {
            
if (tree[root].lc==0) tree[root].lc=i;
            
else tree[root].rc=i;
            tree[i].s
=apple[root][i];
            make_tree(i);
        }
}
int tree_dp(int t,int k)
{
    
if (F[t][k]!=-1return F[t][k];
    
if (t==0 || k==0)
    {
        F[t][k]
=0return 0;
    }
    F[t][k]
=0;
    
for (int i=0;i<=k-1;i++)
    {
        
int ls=tree_dp(tree[t].lc,i);
        
int rs=tree_dp(tree[t].rc,k-1-i);
        
if (F[t][k]<ls+rs) F[t][k]=ls+rs;
    }
    F[t][k]
+=tree[t].s;
    
return F[t][k];
}
int main()
{
    scanf(
"%d%d",&n,&q); q++;
    memset(apple,
-1,sizeof(apple));
    
int a,b,s;
    
for (int i=1;i<=n-1;i++)
    {
        scanf(
"%d%d%d",&a,&b,&s);
        apple[a][b]
=s; apple[b][a]=s;
    }
    memset(tree,
0,sizeof(tree));
    memset(vis,
false,sizeof(vis));
    make_tree(
1);
    memset(F,
-1,sizeof(F));
    
int ans=tree_dp(1,q);
    printf(
"%d\n",ans);
    
return 0;
}

posted on 2009-08-24 10:38 开拓者 阅读(1008) 评论(4)  编辑 收藏 引用 所属分类: 树形DP

Feedback

# re: 【Ural 1018 二叉苹果树】 2012-09-12 17:35 fangshs
你的代码是错误的呀!  回复  更多评论
  

# re: 【Ural 1018 二叉苹果树】 2012-09-12 17:44 fangshs
不好意思,试错题了。。。
  回复  更多评论
  

# re: 【Ural 1018 二叉苹果树】 2016-06-18 18:13 24323
代码是错的  回复  更多评论
  

# re: 【Ural 1018 二叉苹果树】 2016-06-18 18:32 24323
我不理解为什么要 q++  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理