如果要将二叉树{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/169121.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • 分布式锁的实现与应用场景对比

    分布式锁的实现与应用场景对比分布式锁在传统的基于数据库的架构中,对于数据的抢占问题往往是通过数据库事务(ACID)来保证的。在分布式环境中,出于对性能以及一致性敏感度的要求,使得分布式锁成为了一种比较常见而高效的解决方案。应用场景介绍:场景1:场景2:某服务提供一组任务,A请求随机从任务组中获取一个任务;B请求随机从任务组中获取一个任务。在理想的情况下,A从任务组中挑选一个任务,任务组删除该任务,B从剩下的的任务中

  • vim保存和退出_vim编辑器保存退出

    vim保存和退出_vim编辑器保存退出退出vim的快捷键,不需要进入命令编辑模式按住shiftzz保存退出zq不保存退出,q表示放弃之所以按住shift,其实是切换大小写在命令编辑模式下::q不保存退出:q!不保存强制退出:wq保存退出,w表示写入,不论是否修改,都会更改时间戳:x保存退出,如果内容未改,不会更改时间戳“:x”和“:wq”的区别如下:(1…

  • 敏捷大数据流程

    敏捷大数据流程

  • CE修改器使用教程 [基础篇]

    CheatEngine一般简称CE,是一个开放源代码的作弊软件,其功能包括:内存扫描、十六进制编辑器、调试工具,CheatEngine自身附带了外挂制作工具,可以用它直接生成外挂工具,CE可以说是目前最优秀的游戏修改器不是之一,这个工具绝对值得你去学习(只要花一点时间就够了)。本篇文章只是转载内容,后期将会以一些单机游戏为重点,讲解飞天,蹲地,无敌,秒杀,等功能的实现,更多实战教程敬请…

  • C语言编写简易病毒[通俗易懂]

    C语言编写简易病毒[通俗易懂]本次实验设计的是一个基于C语言的恶意代码,其执行流程如下:1、在病毒第一次执行时,即检测到注册表的任务管理器没有被禁用,则病毒依次执行以下功能:创建开机启动项,在系统目录路径下面复制文件,将其作为自启动路径;禁用任务管理器;禁用注册表编辑器;联网获取图片并修改桌面背景(重启生效);修改注册表屏蔽用户键盘输入为1(重启生效);删除驱动器盘符,使桌面以及开始菜单快捷方式失

  • mysql数据库select语句用法_mysql数据库select查询语句简单用法「建议收藏」

    mysql数据库select语句用法_mysql数据库select查询语句简单用法「建议收藏」mysqlselect简单用法1、select语句可以用回车分隔$sql=”select*fromarticlewhereid=1″和$sql=”select*fromarticlewhereid=1″,都可以得到正确的结果,但有时分开写或许能更明了一点,特别是当sql语句比较长时2、批量查询数据可以用in来实现$sql=”select*fromarticlewher…

发表回复

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

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