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

news/2024/6/15 14:51:28/文章来源:https://blog.csdn.net/2301_76553467/article/details/137160279

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.luyixian.cn/news_show_1033932.aspx

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

相关文章

65W智能快充—同为科技桌面PDU插座推荐

近10年&#xff0c;移动设备的智能化、功能化已经完全且紧密的融入到我们的基础生活与工作当中。 在常态化的电子设备的应用中&#xff0c;设备的电力续航以及后续的供电充电就尤为重要。 就目前而言&#xff0c;所有消费电子产品中的输入以及充电的接口&#xff0c;usb-c可以…

竞赛 python图像检索系统设计与实现

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; python图像检索系统设计与实现 &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度系数&#xff1a;3分工作量&#xff1a;3分创新点&#xff1a;4分 该项目较为新颖&#xff0c…

华为开源自研AI框架昇思MindSpore应用案例:梯度累加

目录 一、环境准备1.进入ModelArts官网2.使用CodeLab体验Notebook实例 二、案例实现 梯度累加的训练算法&#xff0c;目的是为了解决由于内存不足&#xff0c;导致Batch size过大神经网络无法训练&#xff0c;或者网络模型过大无法加载的OOM&#xff08;Out Of Memory&#xff…

C++之类和对象的中篇

&#x1d649;&#x1d65e;&#x1d658;&#x1d65a;!!&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦ &#x1f44f;&#x1f3fb;‧✧̣̥̇:Solitary_walk ⸝⋆ ━━━┓ - 个性标签 - &#xff1a;来于“云”的“羽球人”。…

分布式任务调度框架XXL-JOB

1、概述 XXL-JOB是一个分布式任务调度平台&#xff0c;其核心设计目标是开发迅速、学习简单、轻量级、易扩展。现已开放源代码并接入多家公司线上产品线&#xff0c;开箱即用。 官方文档&#xff1a;https://www.xuxueli.com/xxl-job/#%E4%BA%8C%E3%80%81%E5%BF%AB%E9%80%9F%E…

BGP实训

BGP基础配置实训 实验拓扑 注&#xff1a;如无特别说明&#xff0c;描述中的 R1 或 SW1 对应拓扑中设备名称末尾数字为 1 的设备&#xff0c;R2 或 SW2 对应拓扑中设备名称末尾数字为2的设备&#xff0c;以此类推&#xff1b;另外&#xff0c;同一网段中&#xff0c;IP 地址的主…

Vue基础配置、组件通信、自定义指令

基础配置 Vue框架已经集成了webpack配置 小注意点 vbase 快速生成vue模板 组件名必须是多词格式(驼峰模式) 具体三种写法: ①小驼峰:abcDef.vue ②大驼峰&#xff1a;AbcDef.vue ③中横线&#xff1a;abc-def.vue 假如文件名不符合多次格式的补救办法&#xff1a; 导出重命名…

分享一种快速移植OpenHarmony Linux内核的方法

移植概述 本文面向希望将 OpenHarmony 移植到三方芯片平台硬件的开发者&#xff0c;介绍一种借助三方芯片平台自带 Linux 内核的现有能力&#xff0c;快速移植 OpenHarmony 到三方芯片平台的方法。 移植到三方芯片平台的整体思路 内核态层和用户态层 为了更好的解释整个内核…

站群CMS系统

站群CMS系统是一种用于批量建立和管理网站的内容管理系统&#xff0c;它能够帮助用户快速创建大量的网站&#xff0c;并实现对这些网站的集中管理。以下是三个在使用广泛的站群CMS系统&#xff0c;它们各具特色&#xff0c;可以满足不同用户的需求。 1. Z-BlogPHP Z-BlogPHP是…

【JavaScript】函数 ④ ( 函数返回值 | 函数返回值语法 return 关键字 | 函数默认返回值 undefined )

文章目录 一、JavaScript 函数返回值1、函数返回值引入2、函数返回值语法3、函数默认返回值4、函数默认返回值 一、JavaScript 函数返回值 1、函数返回值引入 JavaScript 函数 可以 实现某种特定的功能 , 执行完毕后 , 可以返回一个 " 返回值 " ; 当 函数 被调用执行…

Unity LineRenderer的基本了解

在Unity中&#xff0c;LineRenderer组件用于在场景中绘制简单的线条。它通常用于绘制轨迹、路径、激光等效果。 下面来了解下它的基本信息。 1、创建 法1&#xff1a;通过代码创建 using UnityEngine;public class CreateLineRenderer : MonoBehaviour {void Start(){// 创…

华为OD机试 - 查找舆情热词(Java 2024 C卷 100分)

华为OD机试 2024C卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;A卷B卷C卷&#xff09;》。 刷的越多&#xff0c;抽中的概率越大&#xff0c;每一题都有详细的答题思路、详细的代码注释、样例测试…

基于SSM+Jsp+Mysql的美食推荐管理系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

输出100~200之间的素数(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>//实现素数判断函数&#xff1b; int Prime(int number) {//初始化变量值&#xff1b;int divided 2;int JudgementCondition 0;//循环判断素数&#xff1b;wh…

MySQL Innodb 引擎中预防 Update 操作上升为表锁

一、MySQL 如何预防 Update 上升为表锁 在 MySQL 中&#xff0c;进行任何数据的 修改 操作都会进行一定的锁操作&#xff0c;而锁的不同直接导致性能的差异。例如 MyISAM 引擎&#xff0c;更新时采用表锁&#xff0c;并发性较差。而 Innodb 引擎支持事务&#xff0c;更新时采用…

7.1 Mysql shell 定时备份

直接上脚本----linu 定时任务执行 #!/bin/bash# 配置信息 DB_USER"your_username" # 数据库用户名 DB_PASSWORD"your_password" # 数据库密码 DB_NAME"your_database_name" # 要备份的数据库名 BACKUP_DIR"/path/to/backup/directory"…

LiDAR和Camera融合的BEV感知算法-BEVFusion

0. 简述 本次给大家讲解一篇非常经典的融合工作叫 BEVFusion&#xff0c;我们依旧从算法动机&开创性思路、主体结构、损失函数以及性能对比四个方面展开 BEVFusion 有两篇文章&#xff0c;本次主要讲解的是阿里和北大的&#xff1a;BEVFusion: A Simple and Robust LiDAR-…

[leetcode]28. 找出字符串中第一个匹配项的下标

前言&#xff1a;力扣刷题 问题&#xff1a; 给你两个字符串 haystack 和 needle &#xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;。如果 needle 不是 haystack 的一部分&#xff0c;则返回 -1 。 示例&…

CA根证书——https安全保障的基石

HTTPS通信中&#xff0c;服务器端使用数字证书来证明自己的身份。客户端需要验证服务器发送的证书的真实性。这就需要一个可信的第三方机构&#xff0c;即CA&#xff0c;来颁发和管理证书。CA根证书是证书颁发机构层次结构的顶级证书&#xff0c;客户端信任的所有证书都可以追溯…

新手学python还是c?

考虑到个人情况和职业规划是非常重要的。我这里有一套编程入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习编程&#xff0c;不妨点个关注&#xff0c;给个评论222&#xff0c;私信22&#xff0c;我在后台发给你。 Python作为初学者入门语言…