如果要将二叉树{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)


相关推荐

  • eplan永久激活码【2021免费激活】「建议收藏」

    (eplan永久激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • Hans Berger脑电图之父的人生摘要「建议收藏」

    Hans Berger脑电图之父的人生摘要「建议收藏」摘要:在1938年当脑电图被学术界接受之时,第二次世界大战要开始了,因为英美法都是敌对国,Berger访美计划搁浅。同时大概因为只是英美法学者对脑电图重视,德国本土学者根本不相信,德国当时的纳粹政权禁止研究脑电图。【转载】HansBerger(1873-1941)(上图)是德国精神病学家,精神生理学家,他对神经科学的贡献是发明了和命名了脑电图-Electroencephalography,EEG,德语是Elektrenkephalogramm。此外,Berger发现了“阿尔法波-AlphaWave”,

  • android定时器取消,Android定时器崩溃取消

    android定时器取消,Android定时器崩溃取消我有一个定时器运行,然后熄灭,并做了一些事情,定时器启动罚款。Android定时器崩溃取消然后我想要做的是点击一个按钮,然后创建一个电子邮件。除了在计时器运行时单击该按钮之外,一切正常,应用程序崩溃。当按下按钮时试图取消计时器时,也会使应用程序崩溃。任何帮助,将不胜感激。下面的代码片段:publicclassmyApplicationextendsActivity{StringBuild…

  • Jlink或者stlink用于SWD接口下载程序

    Jlink或者stlink用于SWD接口下载程序最近要使用stm32f103c8t6最小系统板,直接ISP串口下载程序太麻烦,就想着使用swd接口来调试。结果:通过SWD接口下载程序成功,但调试失败,还不知原因,会的的人麻烦交流一下。SWD接口:3.3VDIO(数据)CLK(时钟)GND1.首先声明jlink和stlink都有jtag和swd调试功能。jlink接口如下:如图,我使用的就是VCC…

  • Java内存管理-探索Java中字符串String(十二)

    做一个积极的人编码、改bug、提升自己我有一个乐园,面向编程,春暖花开!文章目录一、初识String类二、字符串的不可变性三、字符串常量池和 intern 方法四、面试题1、 String s1 = new String(“hello”);这句话创建了几个字符串对象?2、有时候在面试的时候会遇到这样的问题:**都说String是不可变的,为什么我可以这样做呢,String a = “1”…

  • Uniapp进行APP打包——iOS 系统[通俗易懂]

    1、创建唯一标识符(1)首先,申请苹果开发者账号。没有苹果开发者账号是无法进行ios打包上线的。(2)进入https://developer.apple.com这个网址,点击“account”并输入苹果开发者账号进入用户界面。(3)点击证书文件(4)进入到这界面以后,点击“APPIDs”,并新建一个APPid(5)设置name和BundleID注意,这个BundleID的格式不要写错在后面多处都会用到。(6)配置相应服务,并点击con

发表回复

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

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