搜索与图论——Kruskal算法求最小生成树

kruskal算法相比prim算法思路简单,不用处理边界问题,不用堆优化,所以一般稀疏图都用Kruskal。

Kruskal算法时间复杂度O(mlogm)

每条边存结构体里,排序需要在结构体里重载小于号

判断a,b点是否连通以及将点假如集合中需要并查集的知识

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 100010, M = 200010;int n, m;
int p[N];struct Edge
{int a, b, w;bool operator< (const Edge& W)const{return w < W.w;}
}edges[M];int find(int x)
{if(p[x] != x) p[x] = find(p[x]);return p[x];
}int Kruskal()
{int res = 0,cnt = 0;for(int i = 1; i <= n; i ++ ){p[i] = i;}for(int i = 0; i < m; i ++ ){int a = find(edges[i].a), b = find(edges[i].b);if(a != b){p[a] = b;res += edges[i].w;cnt ++ ;}}if(cnt < n - 1) return 0;else return res;
}int main()
{cin >> n >> m;for(int i = 0; i < m; i ++ ){int a, b, w;cin >> a >> b >> w;edges[i].a = a, edges[i].b = b, edges[i].w = w;}sort(edges, edges + m);int t = Kruskal();if(!t) cout << "impossible" << endl;else cout << t << endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/292072.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux重点思考(下)--shell脚本使用以及内核开发

Linux重点思考(下&#xff09;--shell脚本使用和组合拳 shell脚本的基础算法shell脚本写123...n的值&#xff0c;说思路Shell 脚本用于执行服务器性能测试的死循环Shell 脚本备份和定时清理垃圾文件 shell脚本的内核开发正向映射反向映射 shell脚本的基础算法 shell脚本写123……

link 样式表是否会阻塞页面内容的展示?取决于浏览器,edge 和 chrome 会,但 firefox 不会。

经过实测&#xff1a; 在 head 中 link 一个 1M 大小的样式表。设置网络下载时间大概为 10 秒。 edge 和 chrome 只有在下载完样式表后&#xff0c;页面上才会出现内容。而 firefox 可以直接先显示内容&#xff0c;然后等待样式表下载完成后再应用样式。 DOMContentLoaded 事…

vue系统——v-html

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>v-html指令</title> </head> <body&…

OSPF基本原理和概念

文章目录 背景知识OSPF协议概述&#xff1a;OSPF区域的表示OSPF 骨干区域 –区域0OSPF 非骨干区域 -非0区域OSPF的五种区域类型OSPF工作原理OSPF 的报文类型OSPF邻居表中的七个状态 总结 背景知识 一台路由设备如何获取其他网段的路由&#xff0c;并加入到路由表中 直连路由 …

虚拟机 centos 安装后与主机 ip保持一致

1、安装时 网络模式 悬着自动检测 &#xff08;桥接&#xff09; 2、打开网络 这里如果没有打开 就去 编辑 该文件。把ONBOOTno 改为yes 后 vim /etc/sysconfig/network-scripts/ifcfg-ens160 刷新配置 systemctl restart network 再查看addr 与本机 192.168.31.xx 在同…

Java23种常见设计模式汇总

七大原则网站地址&#xff1a;设计模式7大原则&#xff0b;类图关系-CSDN博客 创建型设计模式&#xff1a;创建型设计模式合集-CSDN博客 七大结构型设计模式&#xff1a;7大结构型设计模式-CSDN博客 11种行为型设计模式&#xff1a; 11种行为型模式&#xff08;上&#xff0…

设计模式之装饰模式精讲

概念&#xff1a;动态地给一个对象添加一些额外的职责。 装饰器模式侧重于在不改变接口的前提下动态地给对象添加新功能&#xff0c;保持对象结构的透明性&#xff0c;客户端无感知。 以一个咖啡制作和装饰的例子来帮助大家理解&#xff1a; public interface Coffee {double…

基于单片机GPS轨迹定位和里程统计系统

**单片机设计介绍&#xff0c;基于单片机GPS轨迹定位和里程统计系统 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机GPS轨迹定位和里程统计系统是一个集成了GPS定位技术、单片机控制以及里程统计功能的综合性系统。该系…

五、postman基础使用案例

postman基础使用 相关案例【传递查询参数】【提交表单数据】【提交JSON数据】 注&#xff1a;postman⼀款⽀持调试和测试的⼯具&#xff0c;开发、测试⼯程师都可以使⽤。方法一般统一为&#xff1a;方法→请求头→请求体→断言 相关案例 【传递查询参数】 访问TPshop搜索商品的…

EXCEL 通过FILES函数获取指定路径中的所有文件名

FILES函数 用途 获取指定文件路径中的所有文件名。 语法 FILES(“路径\*.*”)指定从哪个路径下返回一个文件名。 *.*是通配符&#xff0c;代表所有类型的文件&#xff0c;第一个*是文件名的通配符&#xff0c;第二个* 是文件的后缀名&#xff0c;表示文件类型&#xff0c;如…

【详解】运算放大器工作原理及其在信号处理中的核心作用

什么是运算放大器 运算放大器&#xff08;简称“运放”&#xff09;是一种放大倍数非常高的电路单元。在实际电路中&#xff0c;它常常与反馈网络一起组成一定的功能模块。它是一种带有特殊耦合电路和反馈的放大器。输出信号可以是输入信号的加法、减法、微分和积分等数学运算…

【C#】知识点速通

前言&#xff1a; 笔者是跟着哔站课程&#xff08;Trigger&#xff09;学习unity才去学习的C#&#xff0c;并且C语言功底尚存&#xff0c;所以只是简单地跟着课程将unity所用的C#语言的关键部分进行了了解&#xff0c;然后在后期unity学习过程中加以深度学习。如需完善的C#知识…

什么是nginx正向代理和反向代理?

什么是代理&#xff1f; 代理(Proxy), 简单理解就是自己做不了的事情或实现不了的功能&#xff0c;委托别人去做。 什么是正向代理&#xff1f; 在nginx中&#xff0c;正向代理指委托者是客户端&#xff0c;即被代理的对象是客户端 在这幅图中&#xff0c;由于左边内网中…

深入浅出Java中高效的ConcurrentLinkedQueue队列底层实现与源码分析

咦咦咦&#xff0c;各位小可爱&#xff0c;我是你们的好伙伴——bug菌&#xff0c;今天又来给大家普及Java SE相关知识点了&#xff0c;别躲起来啊&#xff0c;听我讲干货还不快点赞&#xff0c;赞多了我就有动力讲得更嗨啦&#xff01;所以呀&#xff0c;养成先点赞后阅读的好…

.NET CORE使用Redis分布式锁续命(续期)问题

结合上一期 .NET CORE 分布式事务(三) DTM实现Saga及高并发下的解决方案(.NET CORE 分布式事务(三) DTM实现Saga及高并发下的解决方案-CSDN博客)。有的小伙伴私信说如果锁内锁定的程序或者资源未在上锁时间内执行完&#xff0c;造成的使用资源冲突&#xff0c;需要如何解决。本…

【STM32 HAL库SPI/QSPI协议学习,基于外部Flash读取。】

1、SPI协议 简介 SPI 协议是由摩托罗拉公司提出的通讯协议 (Serial Peripheral Interface)&#xff0c;即串行外围设备接口&#xff0c;是 一种高速全双工的通信总线。它被广泛地使用在 ADC、LCD 等设备与 MCU 间&#xff0c;要求通讯速率 较高的场合。 SPI 物理层 SPI 通讯…

优化选址问题 | 基于帝国企鹅算法求解工厂-中心-需求点三级选址问题含Matlab源码

目录 问题代码问题 "帝国企鹅算法"并不是一个广为人知的优化算法,可能是一个特定领域或者特定情境下提出的方法。不过,对于工厂-中心-需求点三级选址问题,它可能是一种启发式优化方法,用于在多个候选位置中选择最优的工厂、中心和需求点位置。 这类问题通常涉及…

css3之2D转换transform

2D转换transform 一.移动&#xff08;translate)(中间用&#xff0c;隔开&#xff09;二.旋转&#xff08;rotate)&#xff08;有单位deg)1.概念2.注意点3.转换中心点&#xff08;transform-origin)&#xff08;中间用空格&#xff09;4.一些例子(css三角和旋转&#xff09; 三…

分类预测 | MATLAB实现BO-CNN-LSTM贝叶斯优化卷积长短期记忆网络多输入分类预测

分类预测 | MATLAB实现BO-CNN-LSTM贝叶斯优化卷积长短期记忆网络多输入分类预测 目录 分类预测 | MATLAB实现BO-CNN-LSTM贝叶斯优化卷积长短期记忆网络多输入分类预测效果一览基本介绍模型搭建程序设计参考资料 效果一览 基本介绍 MATLAB实现BO-CNN-LSTM贝叶斯优化卷积长短期记…

love 2d Lua 俄罗斯方块超详细教程

源码已经更新在CSDN的码库里&#xff1a; git clone https://gitcode.com/funsion/love2d-game.git 一直在找Lua 能快速便捷实现图形界面的软件&#xff0c;找了一堆&#xff0c;终于发现love2d是小而美的原生lua图形界面实现的方式。 并参考相关教程做了一个更详细的&#x…