kruskal求最小生成树
算法思路:
将所有边按照权值的大小进行升序排序,然后从小到大一一判断。
如果这个边与之前选择的所有边不会组成回路,就选择这条边分;反之,舍去。
直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。
筛选出来的边和所有的顶点构成此连通网的最小生成树。
判断是否会产生回路的方法为:使用并查集。
在初始状态下给各个个顶点在不同的集合中。
遍历过程的每条边,判断这两个顶点的是否在一个集合中。
如果边上的这两个顶点在一个集合中,说明两个顶点已经连通,这条边不要。如果不在一个集合中,则要这条边。
//kruskal求最小生成树
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 9;struct Edge
{int a, b, w;bool operator< (const Edge& W) const{return w < W.w;}
} edges[N];int n, m, p[N], res, cnt;int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 0; i < m; ++i){int a, b, w; cin >> a >> b >> w;edges[i] = { a, b, w };}//从小到大排序sort(edges, edges + m);//并查集数组初始化for (int i = 1; i <= n; ++i) p[i] = i;//如果这个边与之前选择的所有边不会组成回路,就选择这条边分;反之,舍去。//判断是否会产生回路的方法为:使用并查集。//每次将未加入的边加入到集合中去for (int i = 0; i < m; ++i){int a = edges[i].a, b = edges[i].b, w = edges[i].w;//不在一个集合里面a = find(a), b = find(b);if (a != b){res += w;cnt++;p[a] = b;//加入集合}}//如果集合中的边数小于n - 1,说明不存在最小生成树if (cnt < n - 1) cout << "impossible";else cout << res;return 0;
}
关于并查集可以看一下我写的这个篇文章: http://t.csdnimg.cn/ClmtA
相关文章:
kruskal求最小生成树
算法思路: 将所有边按照权值的大小进行升序排序,然后从小到大一一判断。 如果这个边与之前选择的所有边不会组成回路,就选择这条边分;反之,舍去。 直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。 筛选出来的边…...
876. 链表的中间结点
876. 链表的中间结点 算法 快慢指针 & 题目特征 需要对链表中的节点进行遍历,并且需要根据节点之间的相对位置或者距离进行操作 题目链接:https://leetcode.cn/problems/middle-of-the-linked-list/ 算法 快慢指针 & 题目特征 需要对链表中…...
【机器学习】二、决策树
目录 一、决策树定义: 二、决策树特征选择 2.1 特征选择问题 2.2 信息增益 2.2.1 熵 2.2.2 信息增益 三、决策树的生成 3.1 ID3算法 3.1.1理论推导 3.1.2代码实现 3.2 C4.5 算法 3.2.1理论推导 3.2.2代码实现 四、决策树的剪枝 4.1 原理 4.2 算法思路:…...
低代码PAAS加速推进企业数字化转型
无论是“十四五”规划从国家层面提出的“加快数字化发展 建设数字中国”,还是后疫情时代企业自身的感受,数字化转型已成为必答题。当前 企业 业务场景化、线上趋势愈加明显,越来越多并发的数字化应用场景,而原有集中式架构扩展能力…...
时间复杂度为 O(nlogn) 的排序算法
归并排序 归并排序遵循 分治 的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立原问题的解,归并排序的步骤如下: 划分:分解待排序的 n 个元素…...
掌控你的Mac性能:System Dashboard Pro,一款专业的系统监视器
作为Mac用户,你是否曾经想要更好地了解你的电脑性能,以便优化其运行?是否想要实时监控系统状态,以便及时发现并解决问题?如果你有这样的需求,那么System Dashboard Pro就是你的不二之选。 System Dashboar…...
C++ Qt如何往Windows AppData目录写数据
在使用Qt开发客户端软件时,我们可以把程序相关信息保存到AppData目录, 下次启动时读取,就可以保存程序的状态,便于用户使用。 Windows AppData目录是Windows操作系统中的一个重要目录,主要用于存储应用程序的自定义设置、文件和数据。这个目录包含了许多与应用程序相关的配…...
xargs命令
xargs命令 xargs 命令是一个非常好用的 Linux 命令,它可以将管道或标准输入转换成命令行参数,并用这些参数来执行指定 的命令。默认情况下, xargs 命令会将输入按照空格、制表符、换行符等符号进行分隔,并将它们作为一组参数 传…...
【原创】java+swing+mysql无偿献血管理系统设计与实现
摘要: 无偿献血管理系统是为了实现无偿献血规范化、有序化、高效化的管理而设计的。本文主要介绍使用java语言开发一个基于C/S架构的无偿献血管理系统,提高无偿献血管理的工作效率。 功能分析: 系统主要提供给管理员、无偿献血人员&#x…...
C语言 Number 1 基本数据类型
数据类型的定义 c语言的数据分类基本类型整型浮点型float和double的精度和范围范围精度 枚举类型空类型派生类型派生的一般表达形式 注 c语言的数据分类 首先是针对C语言的数据类型做个整理 大致分为四个大类型 基本类型枚举类型空类型派生类型 那么根据以上四个大类型 我们…...
mac录屏快捷键指南,轻松录制屏幕内容!
“大家知道mac电脑有录屏快捷键吗,现在录屏不太方便,每次都花很多时间,要是有录屏快捷键,应该会快速很多,可是哪里都找不到,有人知道吗?帮帮我!” 苹果的mac电脑以其精美的设计和卓…...
精准测试是个错误
如果你已经了解了精准测试在行业的主流做法,你可以跳过相关内容。 行业里对于精准测试的定义 在网上流传着一些精准测试的定义(如果你对这些定义不感冒,可直接跳到我个人的定义): 自网易陈逸青(2020&#x…...
算法通关村第四关|黄金挑战|表达式问题
1.计算器问题 给定一个内容为表达式的字符串,计算结果。 class Solution {public int calculate(String s) {Deque<Integer> stack new ArrayDeque<Integer>();char preSign ;int num 0;int n s.length();for (int i 0; i < n; i) {if (Chara…...
Mac安装DBeaver
目录 一、DBeaver Mac版软件简介 二、下载地址 三、DBeaver连接失败报错 3.1 问题描述 3.2 连接失败问题解决 一、DBeaver Mac版软件简介 DBeaver Mac版是一款专门为开发人员和数据库管理员设计的免费开源通用数据库工具。软件的易用性是它的宗旨,是经过精心设计…...
C++ 类 根据成员变量的指针获取类对象的指针
一.宏定义 实现方式有多种,原理是相同的 方式1: #define get_class_ptr(memberPtr,classType,memberName) \ ((classType*)((char*)(memberPtr)-(unsigned long)((ULONG_PTR)&((classType*)0)->member))) 方式2: #define get_cl…...
图论08-图的建模-状态的表达与理解 - 倒水问题为例
文章目录 状态的表达例题1题解1 终止条件:有一个数位为42 状态的改变:a表示十位数,b表示个位数3 其他设置 例题2 力扣773 滑动谜题JavaC 状态的表达 例题1 从初始的(x,y)状态,到最后变成(4,&am…...
sqlserver字符串拼接
本文主要介绍了sqlserver字符串拼接的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值。 1. 概 在SQL语句中经常需要进行字符串拼接,以sqlserver,oracle,mysql三种数据库为例&#…...
MySQL-----事务
事务的概念 事务是一种机制,一个操作序列。包含了一组数据库的操作命令,所有的命令都是一个整体,向系统提交或者撤销的操作,要么都执行,要么都不执行。 是一个不可分割的单位 事务的ACID特点 ACID,是指在可…...
hive的安装配置笔记
1.上传hive安装包 2.解压 3.配置Hive(在一台机器上即可) mv hive-env.sh.template hive-env.sh 4.运行hive 发现内置默认的metastore存在问题(1.换执行路径后,原来的表不存在了。2.只能有一个用户访问同一个表) 5.配置mysql的meta…...
lamba stream处理集合
lamba stream处理集合 带拼接多字段分组List< Object> 转 Map<String,List< Object>> Map<String, List<ProfitAndLossMapping>> collect plMappingList.stream() .collect(Collectors.groupingBy(m -> m.getLosType() ":" m.…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
