根能抵达的节点(二分法、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常用的提权方法有:系统内核溢出漏洞提权、数据库提权、错误的系统配置提权、组策略首…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
