备战蓝桥杯---图论之最小生成树
首先,什么是最小生成树?
他就是无向图G中的所有生成树中树枝权值总和最小的。
如何求?
我们不妨采用以下的贪心策略:
Prim算法(复杂度:(n+m)logm):
我们对于把上述的点看成两个集合,一个是确定了最小生成树的点,一个还没有确定,我们只要不断把距离已经确定的集合的最短的边添加进去即可。假如我们加的距离不是最小的,那么当我们假设未确定的点已经构成了他们点的最小生成树,那么我们此时用距离最小的去添加他们肯定更优。(我们对于那先未确定的点的集合,不管用什么边去联系他们任何一个点,都不会影响他们以后的最小生成树的形状,这也是贪心当前最优解可以推出全局最优解的保证)
来道模板题:

因为传递消息,至少连n-1条边,又要距离min,相当于求最小生成树,下面是AC代码(我们可以优化一下,对于还未拿出的边,若有一个比他长的则不放入队列):
#include<bits/stdc++.h>
using namespace std;
int n,m,head[100010],a,b,v,cnt,sum;
struct node{int len,dian,next;
}edge[1000005];
void addedge(int x,int y,int v){edge[++cnt].len=v;edge[cnt].dian=y;edge[cnt].next=head[x];head[x]=cnt;
}
int dis[100010];
struct ty{int bian,name;bool operator<(const ty &a) const{return bian>a.bian;}
};
bool vis[1000001];
priority_queue<ty> q;
int prim(){q.push({0,1});while(!q.empty()){ty ck=q.top();q.pop();if(vis[ck.name]==1) continue;vis[ck.name]=1;sum+=ck.bian;for(int i=head[ck.name];i!=-1;i=edge[i].next){if(vis[edge[i].dian]==1) continue;if(dis[edge[i].dian]<=edge[i].len) continue;dis[edge[i].dian]=edge[i].len;q.push({edge[i].len,edge[i].dian});}}return sum;
}
int main(){memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));cin>>n>>m;for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&v);addedge(a,b,v);addedge(b,a,v);}cout<<prim();
}
Kruskal算法(复杂度:mlogm):
还是采取贪心策略,只不过这次是直接选所有边下的最短边,若他们连起来还是树,就连起来,反之舍弃,用并查集维护即可。
首先,我们注意到如果每一次都可以选min的n-1条边就是最优的情况。
但是,在实际上,可能边会在同一个并查集中,说明这条边可以发挥构成树的作用,当时已经存在一点,他的作用是一样的,但是它的距离更小,因此更优。换句话说,我们就是在选n-1个在构建生成树的发挥不同作用的边,而之所以要放弃,是因为功能的重叠。
综上,这样选取的策略最优。
下面给出AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[100010],a,b,v,cnt,sum;
struct node{int len,x,y;
}edge[1000005];
bool cmp(node a,node b){return a.len<b.len;
}
int find(int x){if(fa[x]==x) return x;else return fa[x]=find(fa[x]);
}
void merge(int x,int y){fa[find(x)]=find(y);
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&v);edge[++cnt].x=a;edge[cnt].y=b;edge[cnt].len=v;}sort(edge+1,edge+1+m,cmp);for(int i=1;i<=m;i++){int xx=find(edge[i].x);int yy=find(edge[i].y);if(xx==yy) continue;sum+=edge[i].len;merge(xx,yy);}cout<<sum;
}
相关文章:
备战蓝桥杯---图论之最小生成树
首先,什么是最小生成树? 他就是无向图G中的所有生成树中树枝权值总和最小的。 如何求? 我们不妨采用以下的贪心策略: Prim算法(复杂度:(nm)logm): 我们对于把上述的点看成两个集…...
爬虫-华为云空间备忘录导出到docx-selenium控制浏览器行为-python数据处理
背景适用情况介绍 老的荣耀手机属于华为云系统,家里人换了新荣耀手机属于荣耀云系统无法通过云空间将备忘录转移到新手机,不想让他们一个一个搞,于是整了一晚上想办法爬取下来。从网页抓取下来,然后存到docx文档中(包…...
网络安全的新防线:主动进攻,预防为先
进攻性安全(Offensive security)是指一系列主动安全策略,这些策略与恶意行为者在现实世界的攻击中使用的策略相同,区别在于其目的是加强而非损害网络安全。常见的进攻性安全方法包括红队、渗透测试和漏洞评估。 进攻性安全行动通常…...
基于java springboot+mybatis学生学科竞赛管理管理系统设计和实现
基于java springbootmybatis学生学科竞赛管理管理系统设计和实现 🍅 作者主页 央顺技术团队 🍅 欢迎点赞 👍 收藏 ⭐留言 📝 🍅 文末获取源码联系方式 📝 🍅 查看下方微信号获取联系方式 承接各…...
秒懂百科,C++如此简单丨第二十一天:栈和队列
目录 前言 Everyday English 栈(Stack) 图文解释 实现添加删除元素 实现查看清空栈 完整代码 运行示例 栈的选择题 队列(Queue) 图文解释 队列的基本用法 完整代码 运行结果 队列的好处 结尾 前言 今天我们将…...
STM32-开发环境之STM32CubeMX
目录 STM32CubeMX介绍 STM32CubeMX特性 应用场景 其他事项 STM32CubeMX介绍 STM32CubeMX是ST公司(意法半导体)推出的一款图形化工具,也是配置和初始化C代码生成器。它主要服务于STM32微控制器的配置和开发。 STM32CubeMX特性 1.直观选…...
[晓理紫]CCF系列会议截稿时间订阅
CCF系列会议截稿时间订阅 VX 关注{晓理紫},每日更新最新CCF系列会议信息,如感兴趣,请转发给有需要的同学,谢谢支持!! 如果你感觉对你有所帮助,请关注我,每日准时为你推送最新CCF会议…...
重复导航到当前位置引起的。Vue Router 提供了一种机制,阻止重复导航到相同的路由路径。
代码: <!-- 侧边栏 --><el-col :span"12" :style"{ width: 200px }"><el-menu default-active"first" class"el-menu-vertical-demo" select"handleMenuSelect"><el-menu-item index"…...
如何在 Angular 中使用 Flex 布局
介绍 Flex Layout 是一个组件引擎,允许您使用 CSS Flexbox 创建页面布局,并提供一组指令供您在模板中使用。 该库是用纯 TypeScript 编写的,因此不需要外部样式表。它还提供了一种在不同断点上指定不同指令以创建响应式布局的方法。 在本教…...
通俗的讲解什么是机器学习之损失函数
想象一下,你在玩一个靶心射击的游戏,你的目标是尽可能让箭簇命中靶心。在这个游戏中,损失函数可以看作是测量你的箭簇与靶心距离的规则。损失函数的值越小,意味着你的箭簇离靶心越近,你的射击技能越好。 在机器学习中…...
快速搭建PyTorch环境:Miniconda一步到位
快速搭建PyTorch环境:Miniconda一步到位 🌵文章目录🌵 🌳一、为何选择Miniconda搭建PyTorch环境?🌳🌳二、Miniconda安装指南:轻松上手🌳🌳三、PyTorch与Minic…...
图灵日记之java奇妙历险记--抽象类和接口
目录 抽象类概念抽象类语法 接口概念规则使用特性实现多个接口接口的继承接口使用实例Clonable接口和深拷贝抽象类和接口的区别 Object类 抽象类 概念 在面向对象的概念中,所有对象都是通过类来描述的,但是反过来,并不是所有的类都是用来描绘对象的,如果一个类中没有包含足够…...
批量给元素添加进场动画;获取文本光标位置;项目国际化
批量给元素添加进场动画 api及参数参考:https://juejin.cn/post/7310977323484971071 简单实现: addAnimationClass(){//交叉观察器if (window?.IntersectionObserver) {//获取所有需要添加进场动画的元素,放到一个数组let items [...do…...
解决:docker创建Redis容器成功,但无法启动Redis容器、也无报错提示
解决:docker创建Redis容器成功,但无法启动Redis容器、也无报错提示 一问题描述:1.docker若是直接简单使用run命令,但不挂载容器数据卷等参数,则可以启动Redis容器2.docker复杂使用run命令,使用指定redis.co…...
Jlink+OpenOCD+STM32 Vscode 下载和调试环境搭建
对于 Mingw 的安装比较困难,国内的网无法正常在线下载组件, 需要手动下载 x86_64-8.1.0-release-posix-seh-rt_v6-rev0.7z 版本的软件包,添加环境变量,并将 mingw32-make.exe 名字改成 make.exe。 对于 OpenOCD,需要…...
单片机在物联网中的应用
单片机,这个小巧的电子设备,可能听起来有点技术性,但它实际上是物联网世界中的一个超级英雄。简单来说,单片机就像是各种智能设备的大脑,它能让设备“思考”和“行动”。由于其体积小、成本低、功耗低、易于编程等特点…...
16.Qt 工具栏生成
目录 前言: 技能: 内容: 1. 界面添加 2. 信号槽 功能实现 参考: 前言: 基于QMainWindow,生成菜单下面的工具栏,可以当作菜单功能的快捷键,也可以完成新的功能 直接在UI文件中…...
【Linux内核】从0开始入门Linux Kernel源码
🌈 博客个人主页:Chris在Coding 🎥 本文所属专栏:[Linux内核] ❤️ 前置学习专栏:[Linux学习]从0到1 ⏰ 我们仍在旅途 目录 …...
SQL Service 2008 的安装与配置
点击添加当前用户...
Apache POI | Java操作Excel文件
目录 1、介绍 2、代码示例 2.1、将数据写入Excel文件 2.2、读取Excel文件中的数据 🍃作者介绍:双非本科大三网络工程专业在读,阿里云专家博主,专注于Java领域学习,擅长web应用开发、数据结构和算法,初步…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
