根能抵达的节点(二分法、DFS)C++
给定一棵由 N个节点构成的带边权树。节点编号从 0到 N−1,其中 0 号点为根节点。最初,从根节点可以抵达所有节点(包括自己)。如果我们将所有边权小于 X 的边全部删掉,那么从根节点可以抵达的节点数目就可能发生改变。
现在,给定一个整数 Y,请你找到最小的非负整数 X,使得所有边权小于 X
的边都被删掉以后,根节点能够抵达的节点数目(包括自己)不超过 Y。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。每组数据第一行包含两个整数 N,Y。
接下来 N−1行,每行包含三个整数 U,V,W,表示点 U 和点 V 之间存在一条权值为 W 的边。
输出格式
每组数据输出一行,一个 X。
注意,X 应不小于 0。
数据范围
1≤T≤100,
1≤N≤20000,
1≤Y≤N,
0≤U,V<N,
0≤W≤107,
保证在一个测试点中,所有 N 的和不超过 105。
输入样例:
2
3 2
0 1 2
0 2 3
6 3
0 1 8
0 2 3
1 3 2
1 4 5
2 5 6
输出样例:
3
4
#include<iostream>
#include<cstring>
using namespace std;
const int N=20010,M=N*2;
int h[N],e[M],ne[M],w[M],idx; //头结点、邻接表结点、指针、权、插入的第几个结点。
void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs(int u,int mid,int fa) //从第u个节点遍历,mid为答案,fa为父节点
{int res=1; //从父节点开始可以遍历到的节点for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa||w[i]<mid) continue;//如果次节点边权小于答案,说明该节点被删除后无法到达根节点。res+=dfs(j,mid,u);}return res;
}
int main()
{int T;cin>>T;while(T--){int n,y;cin>>n>>y;idx=0; //每次输出将邻接表清空memset(h,-1,sizeof(h));for(int i=0;i<n-1;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c); //树为特殊的无向图add(b,a,c);}int l=0,r=1e8;while(l<r){int mid=(l+r)/2;if(dfs(0,mid,-1)<=y) r=mid; //当答案小于y时说明答案在y左边,r=mid;else l=mid+1;}cout<<r<<endl;}return 0;
}
相关文章:
根能抵达的节点(二分法、DFS)C++
给定一棵由 N个节点构成的带边权树。节点编号从 0到 N−1,其中 0 号点为根节点。最初,从根节点可以抵达所有节点(包括自己)。如果我们将所有边权小于 X 的边全部删掉,那么从根节点可以抵达的节点数目就可能发生改变。 …...
一天一个设计模式---桥接模式
概念 桥接器模式是一种结构型设计模式,旨在将抽象部分与实现部分分离,使它们可以独立变化而不相互影响。桥接器模式通过创建一个桥接接口,连接抽象和实现,从而使两者可以独立演化。 具体内容 桥接器模式通常包括以下几个要素&a…...
OpenHarmony4.0Release系统应用常见问题FAQ
前言 自OpenHarmony4.0Release发布之后,许多小伙伴使用了配套的系统应用源码以及IDE作为基线开发,也遇到了各种各样的问题,这篇文档主要收录了比较常见的一些问题解答。 FAQ 系统应用源码在哪 目前OpenHarmony系统应用分为3种模式&#x…...
Skywalking UI页面中操作的各种实用功能汇总
刚刚接触skywalking不久,在这里总结一下在UI页面中操作的各种实用功能,随着使用的不断深入,我也会对文章进行持续补充。 本文skywalking 的ui入口是官方demo ,版本是10.0.0-SNAPSHOT-593bd05 http://demo.skywalking.apache.org…...
springboot摄影跟拍预定管理系统源码和论文
首先,论文一开始便是清楚的论述了系统的研究内容。其次,剖析系统需求分析,弄明白“做什么”,分析包括业务分析和业务流程的分析以及用例分析,更进一步明确系统的需求。然后在明白了系统的需求基础上需要进一步地设计系统,主要包罗软件架构模式、整体功能模块、数据库设计。本项…...
【python】python新年烟花代码【附源码】
欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 新年的钟声即将敲响,为了庆祝这个喜庆的时刻,我们可以用 Python 编写一个炫彩夺目的烟花盛典。本文将详细介绍如何使用 Pygame 库创建一个令人惊叹的烟花效果。 一、效果图: 二…...
书生·浦语大模型实战营-学习笔记1
目录 书生浦语大模型全链路开源体系数据集预训练微调评测部署多智能体 视频地址: (1)书生浦语大模型全链路开源体系 开源工具github: https://github.com/InternLM/InternLM 书生浦语大模型全链路开源体系 这次视频中介绍了由上海人工智能实验室OpenMMLa…...
ELF解析03 - 加载段
本文主要讨论 mmap 函数以及如何使用 mmap 函数来加载一个 ELF 的可加载段。 01纠错 Android 8 及以后是会读取 section header 的,但不是所有的 section 都会读取。 https://cs.android.com/android/platform/superproject/main//main:bionic/linker/linker_phdr…...
Mysql——索引相关的数据结构
索引 引入 我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),这种复杂度为…...
无代码DIY图像检索
软件环境准备 可参见《HuggingFists-低代码玩转LLM RAG-准备篇》中的HuggingFists安装及Milvus安装。 流程环境准备 图片准备 进入HuggingFists内置的文件系统,数据源->文件系统->sengee_fs_settings_201创建Image文件夹将事先准备的多张相同或不同种类的图…...
Elasticsearch--Master选举
角色 主节点(active master):一般指的是活跃的主节点,避免负载任务,主节点主要用来管理集群,专用master节点仍将充当协调节点 候选节点(master-eligible nodes):默认具备…...
微服务实战系列之Filter
前言 Filter,又名过滤器,当然不是我们日常中见到的,诸如此类构件: 而应该是微服务中常使用的,诸如此类(图片来自官网,点击可查看原图): 一般用于字符编码转换…...
使用GPT大模型调用工具链
本文特指openai使用sdk的方式调用工具链。 安装openai pip install openai export OPENAI_API_KEY"YOUR OPENAI KEY" 定义工具函数 from openai import OpenAI import jsonclient OpenAI() #工具函数 def get_current_weather(location, unit"fahrenheit&q…...
C语言实现bmp图像底层数据写入与创建
要用C语言实现bmp图像底层数据写入进而创建一张bmp图像,需要对bmp图像文件格式非常了解,如果不太熟悉bmp图像文件格式请先移步bmp图像文件格式超详解 创建bmp图像文件的方式有很多,比如用halcon,用qt,这些都是把已经画…...
基于BP神经网络的定位算法,基于BP神经网络定位预测
目录 摘要 BP神经网络参数设置及各种函数选择 参数设置 训练函数 传递函数 学习函数 性能函数 显示函数 前向网络创建函数 BP神经网络训练窗口详解 训练窗口例样 训练窗口四部详解 基于BP神经网络的定位算法,基于BP神经网络定位预测 代码下载:基于BP神经网络的定位算法,基于…...
Java Http各个请求类型详细介绍
1. 前言 在Spring Boot框架中,HTTP请求类型是构建Web应用程序的重要组成部分。常见的请求类型包括GET、POST、PUT和DELETE,每种类型都有其特定的用途和特点。本文将详细比较这四种请求类型,帮助您在开发过程中做出明智的选择。 2. GET请求…...
python函数装饰器参数统计调用时间和次数
1 python函数装饰器参数统计调用时间和次数 python在函数装饰器外层定义一个函数生成封闭作用域来保存装饰器入参,供装饰器使用。 1.1 装饰器统计调用时间和次数 描述 通过类的可调用实例装饰器来统计函数每次调用时间和总调用时间,以及调用次数。 …...
机器学习之集成学习AdaBoost
概念 AdaBoost(Adaptive Boosting)是一种迭代的集成学习算法,其主要目标是通过组合多个弱学习器来创建一个强大的模型。以下是AdaBoost算法的主要步骤: 初始化样本权重: 为每个训练样本分配相等的权重,通常设为 w i = 1 N w_i = \frac{1}{N} w...
行云部署成长之路 -- 慢 SQL 优化之旅 | 京东云技术团队
当项目的SQL查询慢得像蜗牛爬行时,用户的耐心也在一点点被消耗,作为研发,我们可不想看到这样的事。这篇文章将结合行云部署项目的实践经验,带你走进SQL优化的奇妙世界,一起探索如何让那些龟速的查询飞起来!…...
Windows权限提升
0x01 简介 提权可分为纵向提权与横向提权: 纵向提权:低权限角色获得高权限角色的权限; 横向提权:获取同级别角色的权限。 Windows常用的提权方法有:系统内核溢出漏洞提权、数据库提权、错误的系统配置提权、组策略首…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
