图论之构造完全图
题目 2398:
信息学奥赛一本通T1489-构造完全图
时间限制: 2s 内存限制: 192MB 提交: 16 解决: 9
题目描述
对于完全图 G,若有且仅有一棵最小生成树为 T,则称完全图 G 是树 T 扩展出的。
给你一棵树 T,找出 T 能扩展出的边权和最小的完全图 G。
输入格式
第一行 N 表示树 T 的点数;
接下来 N−1 行三个整数 Si,Ti,Di ;描述一条边(Si,Ti)权值为 Di ;
保证输入数据构成一棵树。
输出格式
输出仅一个数,表示最小的完全图 G 的边权和。
样例输入
复制
4 1 2 1 1 3 1 1 4 2样例输出
复制
12提示
样例说明
添加 D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。
数据范围:
对于 20% 的数据,N≤10;
对于 50% 的数据,N≤1000;
对于 100% 的数据,N≤105,1≤Di≤105 。
思路:
类似于kruskal建树过程,先找到最小树边,再在此基础上加边,使其成为一个局部完全图。依次进行,最后就得到一个最小权完全图。注意加边时边权应该为最小树边权加1,否则就不满足最小生成树的唯一性。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int p[N]; int cnt[N]; long long ans; struct edge{int a,b,w;bool operator<(edge&W){return w<W.w;} }e[N]; int t; int find(int x){if(x!=p[x]){p[x]=find(p[x]);}return p[x]; } int main() {cin>>t;for(int i=1;i<=t;i++){p[i]=i;cnt[i]=1;}for(int i=1;i<t;i++){int a,b,c;cin>>a>>b>>c;e[i].a=a,e[i].b=b,e[i].w=c;}sort(e+1,e+t);for(int i=1;i<t;i++){int a=e[i].a;int b=e[i].b;int c=e[i].w;int x=find(a);int y=find(b);if(x!=y){p[x]=y;ans+=(long long)(cnt[x]*cnt[y]-1)*(c+1);cnt[y]=cnt[x]+cnt[y];ans+=c;}}cout<<ans; }
相关文章:
图论之构造完全图
题目 2398: 信息学奥赛一本通T1489-构造完全图 时间限制: 2s 内存限制: 192MB 提交: 16 解决: 9 题目描述 对于完全图 G,若有且仅有一棵最小生成树为 T,则称完全图 G 是树 T 扩展出的。 给你一棵树 T,找出 T 能扩展出的边权和最小的完全图 G…...
RDD触发算子:一些常用的触发算子(count、foreach、saveAsTextFile、first)
文章目录 1、count算子功能语法 2、foreach算子功能语法 3、saveAsTextFile算子功能语法 4、first算子功能语法举例 1、count算子 功能 统计RDD集合中元素的个数,返回一个int值 语法 def count(self) -> int2、foreach算子 功能 对RDD中每个元素调用一次参数中…...
搭建RAGFlow
RAGFlow 是一款基于深度文档理解构建的开源 RAG(Retrieval-Augmented Generation)引擎。RAGFlow 可以为各种规模的企业及个人提供一套精简的 RAG 工作流程,结合大语言模型(LLM)针对用户各类不同的复杂格式数据提供可靠…...
css中的box-sizing,记录
border-box:最终高度为height,默认包含padding border等属性 content-box:box-sizing默认值,最终大小为heightpaddingborder 等...
使用useCallback引发对闭包的理解
一、先简单介绍一下闭包: 闭包是 JavaScript 中的重要概念,它指的是一个函数可以“记住”并访问其词法作用域,即使在这个函数的外部被执行。简单来说,闭包是由函数及其相关的环境组合而成的。 闭包的特性 函数内部可以访问外部变量: 闭包…...
gvim添加至右键、永久修改配置、放大缩小快捷键、ctrl + c ctrl +v 直接复制粘贴、右键和还原以前版本(V)冲突
一、将 vim 添加至右键 进入安装目录找到 vim91\install.exe 管理员权限执行 Install will do for you:1 Install .bat files to use Vim at the command line:2 Overwrite C:\Windows\vim.bat3 Overwrite C:\Windows\gvim.bat4 Overwrite C:\Windows\evim.bat…...
腾讯云-COS
COS 对象存储 是一种可扩展的云端数据存储服务。它适用于存储任意类型的文件,并且可以针对这些文件进行访问控制。 CORS 跨域资源共享 是一种机制,它使用额外的HTTP头来告诉浏览器允许一个域上的Web应用请求另一个域上的资源。当需要从一个域名下的网页向…...
蓝桥杯每日真题 - 第16天
题目:(卡牌) 题目描述(13届 C&C B组C题) 解题思路: 题目分析: 有 n 种卡牌,每种卡牌的现有数量为 a[i],所需的最大数量为 b[i],还有 m 张空白卡牌。 每…...
基因组之全局互作热图可视化
引言 PlotHiC 是一个专为 Hi-C 数据可视化分析而设计的 Python 包。Hi-C 技术是一种能够检测染色体三维结构的实验方法,它能揭示 DNA 在细胞核内的三维组织结构。为了更好地展示和解释这些复杂的数据,PlotHiC[1] 可以帮助用户方便地绘制Hi-C 数据的热图。…...
基于Lora通讯加STM32空气质量检测WIFI通讯
目录 目录 前言 一、本设计主要实现哪些很“开门”功能? 二、电路设计原理图 1.电路图采用Altium Designer进行设计: 2.实物展示图片 三、程序源代码设计 四、获取资料内容 前言 随着环境污染问题的日益严重,空气质量的监测与管理已经…...
STM32 极速入门第一天基础拓展 驱动i2c屏幕 ( 使用PlatformIO开发STM32单片机 )
输入输出模式解析 输出模式 在输出模式下,通常不需要设置上下拉电阻. 输出电平由 LL_GPIO_SetOutputPin 和 LL_GPIO_ResetOutputPin 函数直 接控制。 输入模式 在输入模式下,设置上下拉电阻是非常重要的. 输入引脚悬空时可能会导致不确定的电平…...
【WPF】Prism学习(五)
Prism Commands 1.错误处理(Error Handling) Prism 9 为所有的命令(包含AsyncDelegateCommand)提供了更好的错误处理。 避免用try/catch包装每一个方法根据不同遇到的异常类型来提供特定的逻辑处理可以在多个命令之间共享错误处…...
RabbitMQ的基本概念和入门
RabbitMQ 的基本概念和入门 RabbitMQ 是一款流行的开源消息队列中间件,实现了高级消息队列协议(AMQP)。它使用Erlang语言编写,具备高可用性、可扩展性和易用性等特点,广泛应用于各种分布式系统中。本文将详细介绍Rabb…...
Shell脚本6 -- 条件判断if
声明: 本文的学习内容来源于B站up主“泷羽sec”视频【shell编程(4)脚本与用户交互以及if条件判断】的公开分享,所有内容仅限于网络安全技术的交流学习,不涉及任何侵犯版权或其他侵权意图。如有任何侵权问题,…...
经验笔记:从生成 SSH 密钥到成功连接测试(以Gitee为例)
从生成 SSH 密钥到成功连接测试的经验笔记(以Gitee为例) 1. 生成 SSH 密钥对 选择合适的加密算法 ED25519: 密钥长度:私钥 256 位(32 字节),公钥 256 位(32 字节)&#…...
Object.defineProperty和响应式
Object.defineProperty()是一个监听对象属性变化的方法。一般情况下我们是不会直接使用的,或者说我们遇到的场景还没有这么高级。 最有名的例子就是Vue2的响应式实现,就是通过这个方法来实现的。 用起来不难,就是个API,只是用的…...
前端web
题目:制作带有下拉悬停菜单的导航栏 效果图 一、先制作菜单栏 <body> <div id"menu"> <div id"container"> <div class"item">游戏1 <div cla…...
DDNet 服务器配置教程 Linux 环境
DDNet 服务器配置教程 Linux 环境 配置之前可以参考一下官方网址给出的内容 官方网址:DDNet官方 环境说明 OS: Debian 11 安装 可以直接从官网下载,也可以使用这个链接: Linux_DDNet 下载链接 上文中给的链接会因为更新而出现版本落后的情况&#x…...
Vue 2 —监视器实现动态切换表单属性值
目录 一、需求背景 二、监视器语法 三、实例展示 1、HTML部分 2、JS部分 四、使用场景总结 1. 表单验证 2. 动态更新 UI 3. 数据同步 4. 计算属性的替代方案 计算属性的优势 : 简洁性: 监视器的优势 : 灵活性: 多属性依赖: 副…...
Qt_day10_程序打包(完结)
目录 1. 设置图标 2. Debug和Release版本 3. 动态链接库 4. 打包 5. 联系项目要求 Qt开发的程序最终都是要给用户使用的,用户的电脑上不可能装一个Qt的开发环境导入项目使用。因此项目项目开发完成后需要打包——制作成安装包,用户直接下载并安装即可使用…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
