【图论】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…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
