如果要将二叉树{16,14,10,8,7,9,3}_二叉分枝

如果要将二叉树{16,14,10,8,7,9,3}_二叉分枝有一棵二叉苹果树,如果树枝有分叉,一定是分两叉,即没有只有一个儿子的节点。这棵树共 N 个节点,编号为 1 至 N,树根编号一定为 1。我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵苹果树的树枝太多了,需要剪枝。但是一些树枝上长有苹果,给定需要保留的树枝数量,求最多能留住多少苹果。这里的保留是指最终与1号点连通。输入格式第一行包含两个整数 N 和 Q,分别表示树的节点数以及要保留的树枝数量。接下来 N−1 行描述树枝信息,每行三个整数,前两个是它连接的节点的编号,第三个数是这根树枝上

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

有一棵二叉苹果树,如果树枝有分叉,一定是分两叉,即没有只有一个儿子的节点。

这棵树共 N 个节点,编号为 1 至 N,树根编号一定为 1。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。

一棵苹果树的树枝太多了,需要剪枝。但是一些树枝上长有苹果,给定需要保留的树枝数量,求最多能留住多少苹果。

这里的保留是指最终与1号点连通。

输入格式
第一行包含两个整数 N 和 Q,分别表示树的节点数以及要保留的树枝数量。

接下来 N−1 行描述树枝信息,每行三个整数,前两个是它连接的节点的编号,第三个数是这根树枝上苹果数量。

输出格式
输出仅一行,表示最多能留住的苹果的数量。

数据范围
1≤Q<N≤100.
N≠1,
每根树枝上苹果不超过 30000 个。

输入样例:
5 2
1 3 1
1 4 10
2 3 20
3 5 20
输出样例:
21

题解
有依赖的背包问题

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
struct Edge{ 
   
    int v,w,next;
}edge[N * 2];
int head[N],cnt;
int n,V;
void add(int u,int v,int w){ 
   
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
void dfs(int u,int fa){ 
   
    for(int i = head[u];~i;i = edge[i].next){ 
   
        int v = edge[i].v,w = edge[i].w;
        if(v == fa)continue;
        dfs(v,u);
        for(int i = V;i >= 1;i --){ 
   
            for(int j = 0;j <= i - 1;j ++){ 
   
                f[u][i] = max(f[u][i],f[u][i - j - 1] + f[v][j] + w);
            }
        }
    }
}
int main(){ 
   
    cin>>n>>V;
    int x,y,w;
    memset(head,-1,sizeof head);
    for(int i = 0;i < n - 1;i ++){ 
   
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    }
    dfs(1,-1);
    cout<<f[1][V]<<endl;
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168634.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • android m 滑动解锁,滑动解锁Slideunlock[通俗易懂]

    android m 滑动解锁,滑动解锁Slideunlock[通俗易懂]滑动解锁(Slideunlock)在之前的塞班机上可谓光茫四射,惹得一身荣耀,如今登入android市场,依然备受关注,多种解锁截屏法方式,满足不同人的需求。软件介绍滑动解锁(Slideunlock),一款仿Iphone又超越Iphone解锁和加锁的实用软件,华丽百变的UI,多种感应器加锁解锁功能,是您可以做到无需触碰手机即可轻松完成加锁或解锁操作。此软件的Symbian版曾流行国内外,一度在No…

  • JAVABEAN是什么和总结JAVABEAN的两种使用方式

    JAVABEAN是什么和总结JAVABEAN的两种使用方式原文:http://www.blogjava.net/flysky19/articles/88180.html一、 javabean 是什么?Javabean 就是一个类,这个类就定义一系列 get 和 set 方法。 Sosimple !Javabean 就是为了和 jsp 页面传数据化简交互过程而产生的。自己的理解:使用 javabean 和不用 javabean 的

  • mysql左连接查询举例_mysql左右连接查询(有示例图)

    mysql左连接查询举例_mysql左右连接查询(有示例图)小小的连接查询,其实里面有很多学问,今天我就来简单剖析一下。左连接,右连接,内连接的本质:将两个表的数据依据一定条件横向连接起来。给出建表语句:————————————————–createtabletest1(idint,namevarchar(10))createtabletest2(idint,namevarc…

  • vim安装YouCompleteMe 插件

    vim安装YouCompleteMe 插件vim安装youcomplete插件,折磨我好久,装不好硬是要把它装好,结果最后终于装好这个补全的插件。为了需要安装的人少走弯路,我的安装过程如下(主要提供步骤):1、先看你的vim版本是多少。我的是vim7.4.52貌似支持python。但是还是不行说是不支持YCM。 最后只能安装vim8.0,手动安装。 具体可以vim–version看来下python和python3是否

  • 时滞微分方程是什么_时滞微分方程教学大纲

    时滞微分方程是什么_时滞微分方程教学大纲考虑下面的变时滞微分方程试绘制上述含有时变时滞微分方程的图像分析:该方程应该在某个t0时间之后成立,初始值必须是定义在t0之前的一个关于t的单值向量函数phi(t)。我假设t0=0吧,phi(t)=[1;-1];matlab程序:functionddeext0=0;tfinal=5;tspan=[t0,tfinal];sol=dd

  • 一个普通专科生,拿什么拯救你的未来?(精简版)

    一个普通专科生,拿什么拯救你的未来?(精简版)总有人要赢,为什么不能是我!—————科比-布莱恩特原文地址:www.dushunchang.top此文为小Du博客原创出品转载,复制请注明原文出处近来看到一则知乎头条,看完时已潸然泪下。附上原文链接戳这:传送门前言:我的故事由你来倾听,做最好的自己。2021年1月26日,今天是科比布莱恩特逝世一周年,我犹豫了很久,决定以自言的方式缅怀我的老大。大家好,我是一名普通的专科生,来自云南大理,大家都叫喜欢叫我小Du。可能很多人看到我的博客…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号