【图论】kruskal算法
一.介绍
![]()
Kruskal(克鲁斯卡尔)算法是一种用于解决最小生成树问题的贪心算法。最小生成树是指在一个连通无向图中,选择一棵包含所有顶点且边权重之和最小的树。
下面是Kruskal算法的基本步骤:
- 将图中的所有边按照权重从小到大进行排序。
- 创建一个空的最小生成树集合(并查集实现)。
- 遍历排序后的边,依次将边加入最小生成树集合中,但要确保加入的边不会形成环路。
- 如果加入边后不会形成环路,则将该边加入最小生成树集合。
- 如果加入边后会形成环路,(即在同一集合)则跳过该边。
- 重复步骤3,直到最小生成树集合中的边数等于图中顶点数减1,或者遍历完所有边。
- 最终得到的最小生成树集合即为所求的最小生成树。
Kruskal算法的核心思想是通过不断选择权重最小的边,并判断是否形成环路来构建最小生成树。它不需要事先知道图的连通性,而是通过边的选择来逐步连接图中的顶点,直到所有顶点都被连接为止。
需要注意的是,Kruskal算法适用于解决无向图的最小生成树问题,对于有向图则需要使用其他算法,如Prim算法。此外,Kruskal算法也可以处理带有边权重相同的情况。
二.模板题
P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
三.【AC】代码
#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
inline int read(){int ans=0,f=1;char cc=getchar();while(cc<'0' || cc>'9'){if(cc=='-') f=-1;cc=getchar();}while(cc>='0' && cc<='9'){ans=(ans<<1)+(ans<<3)+(cc-'0');cc=getchar();}return ans*f;
}
int n,m,ans=0;
bool flag=0;
int fa[5010];
struct Edge{int u,v,w;
}edge[maxn];
bool cmp(Edge a,Edge b){return a.w<b.w;
}
inline int find(int x){return x==fa[x] ? x : fa[x]=find(fa[x]);
}
inline void merge(int x,int y){int fx=find(x),fy=find(y);fa[fx]=fy;
}
void kruskal(){sort(edge+1,edge+m+1,cmp);int cnt=0;for(int i=1;i<=m;i++){int x=edge[i].u,y=edge[i].v;if(find(x)==find(y)) continue;ans+=edge[i].w;merge(x,y);cnt++;if(cnt==n-1){flag=1;return;} }
}
int main(){//读入数据 n=read();m=read();for(int i=1;i<=m;i++){edge[i].u=read();edge[i].v=read();edge[i].w=read();}for(int i=1;i<=n;i++) fa[i]=i;//调用算法 kruskal();//输出结果if(flag) printf("%d",ans); else printf("orz");return 0;
}
相关文章:
【图论】kruskal算法
一.介绍 Kruskal(克鲁斯卡尔)算法是一种用于解决最小生成树问题的贪心算法。最小生成树是指在一个连通无向图中,选择一棵包含所有顶点且边权重之和最小的树。 下面是Kruskal算法的基本步骤: 将图中的所有边按照权重从小到大进行…...
Django框架:使用channels实现websocket,配置和项目实际使用
一、基本配置 依赖包: Django3.2 django-cors-headers3.5.0 redis4.6.0 #操作redis数据库的 channels3.0.0 #websocket channels-redis4.1.0 #通道层需要,依赖redis包项目目录结构: study_websocket --study_websocket --__init__.py --s…...
基于RK3588+FPGA+AI算法定制的智慧交通与智能安防解决方案
随着物联网、大数据、人工智能等技术的快速发展,边缘计算已成为当前信息技术领域的一个热门话题。在物联网领域,边缘计算被广泛应用于智慧交通、智能安防、工业等多个领域。因此,基于边缘计算技术的工业主板设计方案也受到越来越多人的关注。…...
AI面试官:LINQ和Lambda表达式(一)
AI面试官:LINQ和Lambda表达式(一) 当面试官面对C#中关于LINQ和Lambda表达式的面试题时,通常会涉及这两个主题的基本概念、用法、实际应用以及与其他相关技术的对比等。以下是一些可能的面试题目,附带简要解答和相关案…...
FPGA学习——FPGA利用状态机实现电子锁模拟
文章目录 一、本次实验简介二、源码及分析三、总结 一、本次实验简介 本次是实验是为了利用状态机模拟电子锁,相关要求如下: 顺序输入4位密码,密码为1234,用按键来键入密码用led灯指示键入第几位密码,(博…...
Bert经典变体学习
ALBert ALBERT就是为了解决模型参数量大以及训练时间过长的问题。ALBERT最小的参数只有十几M, 效果要比BERT低1-2个点,最大的xxlarge也就200多M。可以看到在模型参数量上减少的还是非常明显的,但是在速度上似乎没有那么明显。最大的问题就是这种方式其实…...
uniapp checkbox radio 样式修改
文章目录 通过查看代码,发现 before部分是设置样式的主要属性 我们要设置的话,就要设置checkbox::before的属性。 其中的content表示内容,比如内部的对勾 那么我们设置的时候,比如设置disabletrue的时候或者checkedtrue的时候&…...
电脑重启后VScode快捷方式失效,找不到Code.exe
问题描述 下班回家关了部分程序就直接关机了,回家后重启电脑发现vscode的快捷方式就失效了,提示Code.exe已被移动或删除。 解决方法 查看你的vscode安装目录,Microsoft VS Code目录下大概率会存在一个名为_的文件夹,然后会发现…...
C语言实现扫雷游戏
test.c源文件 - 扫雷游戏测试 game.h头文件 - 扫雷游戏函数的声明 game.c源文件 - 扫雷游戏函数的实现 1.布置雷 -- 存放雷的雷盘 9*9 数组设计成11*11 上下左右方各多一行,保证周围8的范围 雷 - 1 不是雷 - 0 2.排查雷 主题测试源文件代码 &…...
蓝图节点编辑器
打印字符串 第02章 蓝图结构 03 -注释和重新路由_哔哩哔哩_bilibili 第02章 蓝图结构 04 - 变量_哔哩哔哩_bilibili 第03章 蓝图简易门 01 - 箱子碰撞_哔哩哔哩_bilibili 第03章 蓝图简易门 02 - 静态Mesh和箭头_哔哩哔哩_bilibili 第03章 蓝图简易门 03 - 设置相对旋转节点_哔…...
MySql 知识大汇总
数据库索引 数据库索引是一种数据结构,用于提高数据库查询的速度和效率。索引可以看作是表中一列或多列的值的快速查找方式,类似于书籍的目录。通过创建索引,可以减少数据库的扫描量,加快数据的检索速度。 常见的索引类型 常见…...
深入浅出Pytorch函数——torch.sum
分类目录:《深入浅出Pytorch函数》总目录 相关文章: 深入浅出Pytorch函数——torch.Tensor 函数torch.sum有两种形式: torch.sum(input, *, dtypeNone):返回输入张量input所有元素的和。torch.sum(input, dim, keepdimFalse, *,…...
Git克隆文件不显示绿色勾、红色感叹号等图标
1、问题 Git和TorToiseGit安装后,Git克隆的文件不会显示绿色勾、红色感叹号等图标。 2、检查注册表 2.1、打开注册表 (1)WinR打开运行窗口,输入regedit,点击确定,打开注册表编辑器。 2.2、找如下路径 (1)找到路径 计算机\HKEY_…...
SOC FPGA之HPS模型设计(一)
目录 一、建立HPS硬件系统模型 1.1 GHRD 1.2 从0开始搭建HPS 1.2.1 FPGA Interfaces 1.2.1.1 General 1.2.1.2 AXI Bridge 1.2.1.3 FPGA-to-HPS SDRAM Interface 1.2.1.4 DMA Peripheral Request 1.2.1.5 Interrupts 1.2.1.6 EMAC ptp interface 1.2.2 Peripheral P…...
解决openstack重启swift服务后报错
swift重启报错 问题描述解决办法 问题描述 swift服务正常状态如下 [rootcontroller ~]# swift statAccount: AUTH_8bde12ff804e42498661b7454994c446Containers: 0Objects: 0Bytes: 0X-Put-Timestamp: 1690507907.67931X-Timestamp: 1690507907.67931X-Trans-Id: tx56d22fa13…...
[Linux]进程控制详解!!(创建、终止、等待、替换)
hello,大家好,这里是bang___bang_,在上两篇中我们讲解了进程的概念、状态和进程地址空间,本篇讲解进程的控制!!包含内容有进程创建、进程等待、进程替换、进程终止!! 附上前2篇文章…...
全面适配 | 走近openGauss数据库+鲲鹏欧拉操作系统
引入 全面适配 | openEuler操作系统 openGauss数据库 开篇 1、openEuler欧拉操作系统 百度百科:openEuler是覆盖全场景的创新平台,在引领内核创新,夯实云化基座的基础上,面向计算架构互联总线、存储介质发展新趋势,…...
2023Robocom CAIP省赛 第四题 相对论大师
原题链接: PTA | 程序设计类实验辅助教学平台 题面: 在某个直播间里,观众常常会发送类似这样的弹幕: 鱼越大,鱼刺越大;鱼刺越大,肉越少;肉越少,鱼越小;所以鱼…...
【TypeScript】TS入门级基础学习(一)
【TypeScript】TS入门级基础学习(一) 一、前言 TypeScript 是一种用于应用程序规模的 JavaScript 语言。 TypeScript 向 JavaScript 添加了可选类型,支持用于任何浏览器、任何主机、任何操作系统的大规模 JavaScript 应用程序的工具。 Type…...
jenkins执行jmeter时,报Begin size 1 is not equal to fixed size 5
jenkins执行jmeter脚本的时候一直提示如下错误: Tidying up ... Fri Jul 28 17:03:53 CST 2023 (1690535033178) Error generating the report: org.apache.jmeter.report.dashboard.GenerationException: Error while processing samples: Consumer failed wi…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
