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

数据结构选讲 (更新中)

参考 smWCDay7 数据结构选讲2 by yyc

可能会补充的:

  • AT_cf17_final_j TreeMSTF2 Boruvka算法

目录

  • AT_cf17_final_j Tree MST

AT_cf17_final_j Tree MST

link
题意
给定一棵 n n n 个点的树,点有点权 w i w_i wi,边有边权。建立一张完全图 G G G,节点 u , v u, v u,v 之间的边长为 w u + w v + d i s ( u , v ) w_u + w_v + dis(u, v) wu+wv+dis(u,v) 。求 G G G M S T MST MST (最小生成树)的边权和。

  • n ≤ 2 × 1 0 5 , 1 ≤ w i ≤ 1 0 9 n \le 2 \times 10^5 ,1 \le w_i \le 10^9 n2×1051wi109

思路
前置指示:点分治

引理:边 e e e 在边集 E E E 的最小生成树中,则对于任意 E 0 ⊆ E E_0 ⊆ E E0E,e 也在边集 E 0 E_0 E0 的最小生成树中。
证明:考虑 kruskal
推论:将边分为若干组,分别求最小生成树,再合并求最小生成树,结果正确。

题目是说建立一张完全图然后求其的 M S T MST MST ,但是这样的边是 n 2 n^2 n2 级别的,考虑去掉一些多余的边,只保留有用的边。所以可以将完全图 G G G 分成很多个边集,分别求 M S T MST MST (不必强制联通),然后保留有用边,最后再综合求 M S T MST MST 就是答案了。
考虑 点分治,以重心为根,将树分成几个子树,那么就只用处理跨越重心的边即可。
d i s i dis_i disi 表示 点 i i i 到重心的距离,跨越重心的边 ( u , v ) (u,v) (u,v),边权是 w u + d i s u + w v + d i s v w_u + dis_u + w_v + dis_v wu+disu+wv+disv 。由于每个点 i i i 都要贡献至少一次 w i + d i s i w_i+dis_i wi+disi,另外一边肯定选最小的 w j + d i s j w_j+dis_j wj+disj ,所以我们只需要选择 w i + d i s i w_i + dis_i wi+disi 最小的点,让它和所有其他点连边,该菊花图就是最小生成树。(在同一棵子树内连了边也不影响结果,因为它们的边权比真实值要大 d i s u + d i s v > d i s u , v dis_u + dis_v \gt dis_{u,v} disu+disv>disu,v )。这样边的数量就减到了 n l o g n nlogn nlogn,总时间复杂度为 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

好像还有一种方法,要用到 Boruvka算法 ,后续可能会学……

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;int idx,head[maxn];
struct EDGE{ int v,next; ll w; }e[maxn*2];
void Insert(int u,int v,ll w){e[++idx]={v,head[u],w};head[u]=idx;
}int siz[maxn],mxson[maxn],pot[maxn],tn;
bool vis[maxn];
void Dfs(int x,int fa){pot[++tn]=x,siz[x]=1,mxson[x]=0;for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(!vis[v]&&v!=fa){Dfs(v,x);siz[x]+=siz[v];mxson[x]=max(mxson[x],siz[v]);}}
}int Get_root(int x){tn=0,Dfs(x,0);int root=0;for(int i=1;i<=tn;i++){mxson[pot[i]]=max(mxson[pot[i]],tn-siz[pot[i]]);if(!root||mxson[root]>mxson[pot[i]]) root=pot[i]; }return root;
}int id;
ll a[maxn],dis[maxn];
void Dfs2(int x,int fa){for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(!vis[v]&&v!=fa){dis[v]=dis[x]+e[i].w;Dfs2(v,x);}}if(!id||a[x]+dis[x]<a[id]+dis[id]) id=x;
}int cnt;
struct EDGE2{ int u,v; ll w; }te[maxn*20];
void Solve(int rt){dis[rt]=0,id=0,Dfs2(rt,0);for(int i=1;i<=tn;i++)te[++cnt]={id,pot[i],a[id]+dis[id]+a[pot[i]]+dis[pot[i]]};vis[rt]=1;for(int i=head[rt];i;i=e[i].next){int v=e[i].v;if(!vis[v]) Solve(Get_root(v));}
}int fa[maxn];
int Find_fa(int x){ return fa[x]==x?x:fa[x]=Find_fa(fa[x]); }int main(){int n; cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<n;i++){int x,y,z; cin>>x>>y>>z;Insert(x,y,z),Insert(y,x,z);}Solve(Get_root(1));sort(te+1,te+cnt+1,[](EDGE2 a,EDGE2 b){ return a.w<b.w; });for(int i=1;i<=n;i++)fa[i]=i;ll ans=0;for(int i=1;i<=cnt;i++){int fx=Find_fa(te[i].u),fy=Find_fa(te[i].v);if(fx!=fy) fa[fy]=fx,ans+=te[i].w;}cout<<ans;return 0;
}

相关文章:

数据结构选讲 (更新中)

参考 smWCDay7 数据结构选讲2 by yyc 。 可能会补充的&#xff1a; AT_cf17_final_j TreeMST 的 F2 Boruvka算法 目录 AT_cf17_final_j Tree MST AT_cf17_final_j Tree MST link 题意 给定一棵 n n n 个点的树&#xff0c;点有点权 w i w_i wi​&#xff0c;边有边权。建立…...

OpenBMC:简介

通常在服务器主板上&#xff0c;有一个独立的微处理器&#xff0c;叫作BMC(Baseboard Manager Controller)&#xff0c;用于与主机(host)进行通信&#xff0c;提供带外的方式查询服务器的状态和信息&#xff0c;并进行管理服务器。 OpenBMC是Linux Foundation的开源BMC项目&am…...

java 正则表达式匹配Matcher 类

Matcher 类 用法 在 Java 中&#xff0c;Matcher 类是用于匹配正则表达式的工具&#xff0c;而 group() 方法是 Matcher 类中的一个重要方法&#xff0c;用于提取匹配结果中的捕获组&#xff08;captured groups&#xff09;。以下是对 group() 方法的详细解释&#xff1a; 1.…...

【HarmonyOS之旅】基于ArkTS开发(三) -> 兼容JS的类Web开发(三)

目录 1 -> 生命周期 1.1 -> 应用生命周期 1.2 -> 页面生命周期 2 -> 资源限定与访问 2.1 -> 资源限定词 2.2 -> 资源限定词的命名要求 2.3 -> 限定词与设备状态的匹配规则 2.4 -> 引用JS模块内resources资源 3 -> 多语言支持 3.1 -> 定…...

CSS(快速入门)

欢迎大家来到我的博客~欢迎大家对我的博客提出指导&#xff0c;有错误的地方会改进的哦~点击这里了解更多内容 目录 一、什么是CSS?二、基本语法规范三、CSS选择器3.1 标签选择器3.2 id选择器3.3 class选择器3.4 通配符选择器3.5 复合选择器 四、常用CSS样式4.1 color4.2 font…...

使用 concurrently 实现前后端一键启动

使用 concurrently 实现前后端一键启动 本文适合&#xff1a; 前后端分离项目&#xff08;如 React Node.js&#xff09;&#xff0c;希望通过一条命令同时启动前端和后端服务。 工具链&#xff1a; Node.js、npm、concurrently。 耗时&#xff1a; 3 分钟。 文章目录 使用 c…...

常见端口的攻击思路

端口号端口说明攻击方向21/22/69FTP/TFTP文件传输协议匿名上传/下载、嗅探、爆破2049NFS服务配置不当139Sanba服务爆破、远程代码执行389Ldap目录访问协议注入、匿名访问、弱口令22SSH远程连接爆破、SSH映射隧道搭建、文件传输23Telnet远程连接爆破、嗅探、弱口令3389RDP远程桌…...

大数据治理实战:架构、方法与最佳实践

&#x1f4dd;个人主页&#x1f339;&#xff1a;一ge科研小菜鸡-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 1. 引言 大数据治理是确保数据质量、合规性和安全性的重要手段&#xff0c;尤其在数据驱动决策和人工智能应用日益普及的背景下&…...

忘记宝塔的访问地址怎么找

在linux中安装宝塔面板后会生成网址、账号和密码 如果网址忘记了那将进不去宝塔面板该怎么办呢&#xff1f; bt命令 我们输入 bt 命令的时候&#xff0c;是在根目录里面进行操作的。 / bt 我们根据自己的需要&#xff0c;选择对应的数字就可以了。 bt 14 输入 14 查看面板默…...

SQL教程-基础语法

INSERT INTO 新增数据 INSERT INTO 数据表名 VALUES (值1,值2,值3,...) DELETE 删除数据 DELETE FROM 数据表名 WHERE 查询条件 UPDATE 修改数据 UPDATE 数据表名 SET 字段1 值1, 字段2值2, ... WHERE 查询条件 SELECT 查询数据 #查询数据 SELECT 字段1, 字段2, ... FROM 数…...

shell脚本批量修改文件名之方法(The Method of Batch Modifying File Names in Shell Scripts)

shell脚本批量修改文件名方法 我们可以使用Shell脚本来实现这个功能。Shell脚本是一种用于自动化任务的编程语言&#xff0c;它可以在Unix/Linux操作系统上运行。在这个脚本中&#xff0c;我们将使用一个for循环来遍历目标目录下的所有文件&#xff0c;并使用mv命令将每个文件…...

组合模式 - 组合模式的实现

引言 组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许你将对象组合成树形结构来表示“部分-整体”的层次结构。组合模式使得客户端可以统一地处理单个对象和组合对象&#xff0c;从而简化了代码的复杂性。本文将详细介绍如何在C中实…...

视频外绘技术总结:Be-Your-Outpainter、Follow-Your-Canvas、M3DDM

Diffusion Models专栏文章汇总:入门与实战 前言:视频Inpaint的技术很火,但是OutPaint却热度不高,这篇博客总结比较经典的几篇视频Outpaint技术。其实Outpaint在runway等工具上很火,可是学术界对此关注比较少,博主从这三年的顶会中找到了最具代表性的三篇论文解读。 目录 …...

【硬件测试】基于FPGA的QPSK+帧同步系统开发与硬件片内测试,包含高斯信道,误码统计,可设置SNR

目录 1.算法仿真效果 2.算法涉及理论知识概要 2.1QPSK 2.2 帧同步 3.Verilog核心程序 4.开发板使用说明和如何移植不同的开发板 5.完整算法代码文件获得 1.算法仿真效果 本文是之前写的文章 《基于FPGA的QPSK帧同步系统verilog开发,包含testbench,高斯信道,误码统计,可…...

c++面试:类定义为什么可以放到头文件中

这个问题是刚了解预编译的时候产生的疑惑。 声明是指向编译器告知某个变量、函数或类的存在及其类型&#xff0c;但并不分配实际的存储空间。声明的主要目的是让编译器知道如何解析程序中的符号引用。定义不仅告诉编译器实体的存在&#xff0c;还会为该实体分配存储空间&#…...

PythonFlask框架

文章目录 处理 Get 请求处理 POST 请求应用 app.route(/tpost, methods[POST]) def testp():json_data request.get_json()if json_data:username json_data.get(username)age json_data.get(age)return jsonify({username: username测试,age: age})从 flask 中导入了 Flask…...

Kotlin开发(六):Kotlin 数据类,密封类与枚举类

引言 想象一下&#xff0c;你是个 Kotlin 开发者&#xff0c;敲着代码忽然发现业务代码中需要一堆冗长的 POJO 类来传递数据。烦得很&#xff1f;别急&#xff0c;Kotlin 贴心的 数据类 能帮你自动生成 equals、hashCode&#xff0c;直接省时省力&#xff01;再想想需要多种状…...

冬天适合养什么鱼?

各位鱼友们&#xff0c;冬天来了&#xff0c;是不是还在为养什么鱼而烦恼&#xff1f;别担心&#xff0c;今天就来给大家好好推荐一些适合冬天养的鱼&#xff0c;让你的水族箱在寒冷的冬天也能生机勃勃&#xff01; 一、金鱼&#xff1a;冬日里的“小暖男” 金鱼绝对是冬季养鱼…...

【C++动态规划 状态压缩】2597. 美丽子集的数目|2033

本文涉及知识点 C动态规划 LeetCode2597. 美丽子集的数目 给你一个由正整数组成的数组 nums 和一个 正 整数 k 。 如果 nums 的子集中&#xff0c;任意两个整数的绝对差均不等于 k &#xff0c;则认为该子数组是一个 美丽 子集。 返回数组 nums 中 非空 且 美丽 的子集数目。…...

前端-Rollup

Rollup 是一个用于 JavaScript 的模块打包工具&#xff0c;它将小的代码片段编译成更大、更复杂的代码&#xff0c;例如库或应用程序。它使用 JavaScript 的 ES6 版本中包含的新标准化代码模块格式&#xff0c;而不是以前的 CommonJS 和 AMD 等特殊解决方案。ES 模块允许你自由…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...