当前位置: 首页 > news >正文

图论之构造完全图

题目 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&#xff0c;若有且仅有一棵最小生成树为 T&#xff0c;则称完全图 G 是树 T 扩展出的。 给你一棵树 T&#xff0c;找出 T 能扩展出的边权和最小的完全图 G…...

RDD触发算子:一些常用的触发算子(count、foreach、saveAsTextFile、first)

文章目录 1、count算子功能语法 2、foreach算子功能语法 3、saveAsTextFile算子功能语法 4、first算子功能语法举例 1、count算子 功能 统计RDD集合中元素的个数&#xff0c;返回一个int值 语法 def count(self) -> int2、foreach算子 功能 对RDD中每个元素调用一次参数中…...

搭建RAGFlow

RAGFlow 是一款基于深度文档理解构建的开源 RAG&#xff08;Retrieval-Augmented Generation&#xff09;引擎。RAGFlow 可以为各种规模的企业及个人提供一套精简的 RAG 工作流程&#xff0c;结合大语言模型&#xff08;LLM&#xff09;针对用户各类不同的复杂格式数据提供可靠…...

css中的box-sizing,记录

border-box&#xff1a;最终高度为height&#xff0c;默认包含padding border等属性 content-box&#xff1a;box-sizing默认值&#xff0c;最终大小为heightpaddingborder 等...

使用useCallback引发对闭包的理解

一、先简单介绍一下闭包: 闭包是 JavaScript 中的重要概念&#xff0c;它指的是一个函数可以“记住”并访问其词法作用域&#xff0c;即使在这个函数的外部被执行。简单来说&#xff0c;闭包是由函数及其相关的环境组合而成的。 闭包的特性 函数内部可以访问外部变量: 闭包…...

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 对象存储 是一种可扩展的云端数据存储服务。它适用于存储任意类型的文件&#xff0c;并且可以针对这些文件进行访问控制。 CORS 跨域资源共享 是一种机制&#xff0c;它使用额外的HTTP头来告诉浏览器允许一个域上的Web应用请求另一个域上的资源。当需要从一个域名下的网页向…...

蓝桥杯每日真题 - 第16天

题目&#xff1a;&#xff08;卡牌&#xff09; 题目描述&#xff08;13届 C&C B组C题&#xff09; 解题思路&#xff1a; 题目分析&#xff1a; 有 n 种卡牌&#xff0c;每种卡牌的现有数量为 a[i]&#xff0c;所需的最大数量为 b[i]&#xff0c;还有 m 张空白卡牌。 每…...

基因组之全局互作热图可视化

引言 PlotHiC 是一个专为 Hi-C 数据可视化分析而设计的 Python 包。Hi-C 技术是一种能够检测染色体三维结构的实验方法&#xff0c;它能揭示 DNA 在细胞核内的三维组织结构。为了更好地展示和解释这些复杂的数据&#xff0c;PlotHiC[1] 可以帮助用户方便地绘制Hi-C 数据的热图。…...

基于Lora通讯加STM32空气质量检测WIFI通讯

目录 目录 前言 一、本设计主要实现哪些很“开门”功能&#xff1f; 二、电路设计原理图 1.电路图采用Altium Designer进行设计&#xff1a; 2.实物展示图片 三、程序源代码设计 四、获取资料内容 前言 随着环境污染问题的日益严重&#xff0c;空气质量的监测与管理已经…...

STM32 极速入门第一天基础拓展 驱动i2c屏幕 ( 使用PlatformIO开发STM32单片机 )

输入输出模式解析 输出模式 在输出模式下&#xff0c;通常不需要设置上下拉电阻. 输出电平由 LL_GPIO_SetOutputPin 和 LL_GPIO_ResetOutputPin 函数直 接控制。 输入模式 在输入模式下&#xff0c;设置上下拉电阻是非常重要的. 输入引脚悬空时可能会导致不确定的电平&#xf…...

【WPF】Prism学习(五)

Prism Commands 1.错误处理&#xff08;Error Handling&#xff09; Prism 9 为所有的命令&#xff08;包含AsyncDelegateCommand&#xff09;提供了更好的错误处理。 避免用try/catch包装每一个方法根据不同遇到的异常类型来提供特定的逻辑处理可以在多个命令之间共享错误处…...

RabbitMQ的基本概念和入门

RabbitMQ 的基本概念和入门 RabbitMQ 是一款流行的开源消息队列中间件&#xff0c;实现了高级消息队列协议&#xff08;AMQP&#xff09;。它使用Erlang语言编写&#xff0c;具备高可用性、可扩展性和易用性等特点&#xff0c;广泛应用于各种分布式系统中。本文将详细介绍Rabb…...

Shell脚本6 -- 条件判断if

声明&#xff1a; 本文的学习内容来源于B站up主“泷羽sec”视频【shell编程&#xff08;4&#xff09;脚本与用户交互以及if条件判断】的公开分享&#xff0c;所有内容仅限于网络安全技术的交流学习&#xff0c;不涉及任何侵犯版权或其他侵权意图。如有任何侵权问题&#xff0c…...

经验笔记:从生成 SSH 密钥到成功连接测试(以Gitee为例)

从生成 SSH 密钥到成功连接测试的经验笔记&#xff08;以Gitee为例&#xff09; 1. 生成 SSH 密钥对 选择合适的加密算法 ED25519&#xff1a; 密钥长度&#xff1a;私钥 256 位&#xff08;32 字节&#xff09;&#xff0c;公钥 256 位&#xff08;32 字节&#xff09;&#…...

Object.defineProperty和响应式

Object.defineProperty()是一个监听对象属性变化的方法。一般情况下我们是不会直接使用的&#xff0c;或者说我们遇到的场景还没有这么高级。 最有名的例子就是Vue2的响应式实现&#xff0c;就是通过这个方法来实现的。 用起来不难&#xff0c;就是个API&#xff0c;只是用的…...

前端web

题目&#xff1a;制作带有下拉悬停菜单的导航栏 效果图 一、先制作菜单栏 <body> <div id"menu"> <div id"container"> <div class"item">游戏1 <div cla…...

DDNet 服务器配置教程 Linux 环境

DDNet 服务器配置教程 Linux 环境 配置之前可以参考一下官方网址给出的内容 官方网址&#xff1a;DDNet官方 环境说明 OS: Debian 11 安装 可以直接从官网下载&#xff0c;也可以使用这个链接: Linux_DDNet 下载链接 上文中给的链接会因为更新而出现版本落后的情况&#x…...

Vue 2 —监视器实现动态切换表单属性值

目录 一、需求背景 二、监视器语法 三、实例展示 1、HTML部分 2、JS部分 四、使用场景总结 1. 表单验证 2. 动态更新 UI 3. 数据同步 4. 计算属性的替代方案 计算属性的优势 : 简洁性&#xff1a; 监视器的优势 : 灵活性&#xff1a; 多属性依赖&#xff1a; 副…...

Qt_day10_程序打包(完结)

目录 1. 设置图标 2. Debug和Release版本 3. 动态链接库 4. 打包 5. 联系项目要求 Qt开发的程序最终都是要给用户使用的&#xff0c;用户的电脑上不可能装一个Qt的开发环境导入项目使用。因此项目项目开发完成后需要打包——制作成安装包&#xff0c;用户直接下载并安装即可使用…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...