当前位置: 首页 > news >正文

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求最小生成树

算法思路&#xff1a; 将所有边按照权值的大小进行升序排序&#xff0c;然后从小到大一一判断。 如果这个边与之前选择的所有边不会组成回路&#xff0c;就选择这条边分&#xff1b;反之&#xff0c;舍去。 直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。 筛选出来的边…...

876. 链表的中间结点

876. 链表的中间结点 算法 快慢指针 & 题目特征 需要对链表中的节点进行遍历&#xff0c;并且需要根据节点之间的相对位置或者距离进行操作 题目链接&#xff1a;https://leetcode.cn/problems/middle-of-the-linked-list/ 算法 快慢指针 & 题目特征 需要对链表中…...

【机器学习】二、决策树

目录 一、决策树定义&#xff1a; 二、决策树特征选择 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 算法思路&#xff1a…...

低代码PAAS加速推进企业数字化转型

无论是“十四五”规划从国家层面提出的“加快数字化发展 建设数字中国”&#xff0c;还是后疫情时代企业自身的感受&#xff0c;数字化转型已成为必答题。当前 企业 业务场景化、线上趋势愈加明显&#xff0c;越来越多并发的数字化应用场景&#xff0c;而原有集中式架构扩展能力…...

时间复杂度为 O(nlogn) 的排序算法

归并排序 归并排序遵循 分治 的思想&#xff1a;将原问题分解为几个规模较小但类似于原问题的子问题&#xff0c;递归地求解这些子问题&#xff0c;然后合并这些子问题的解来建立原问题的解&#xff0c;归并排序的步骤如下&#xff1a; 划分&#xff1a;分解待排序的 n 个元素…...

掌控你的Mac性能:System Dashboard Pro,一款专业的系统监视器

作为Mac用户&#xff0c;你是否曾经想要更好地了解你的电脑性能&#xff0c;以便优化其运行&#xff1f;是否想要实时监控系统状态&#xff0c;以便及时发现并解决问题&#xff1f;如果你有这样的需求&#xff0c;那么System Dashboard Pro就是你的不二之选。 System Dashboar…...

C++ Qt如何往Windows AppData目录写数据

在使用Qt开发客户端软件时,我们可以把程序相关信息保存到AppData目录, 下次启动时读取,就可以保存程序的状态,便于用户使用。 Windows AppData目录是Windows操作系统中的一个重要目录,主要用于存储应用程序的自定义设置、文件和数据。这个目录包含了许多与应用程序相关的配…...

xargs命令

xargs命令 xargs 命令是一个非常好用的 Linux 命令&#xff0c;它可以将管道或标准输入转换成命令行参数&#xff0c;并用这些参数来执行指定 的命令。默认情况下&#xff0c; xargs 命令会将输入按照空格、制表符、换行符等符号进行分隔&#xff0c;并将它们作为一组参数 传…...

【原创】java+swing+mysql无偿献血管理系统设计与实现

摘要&#xff1a; 无偿献血管理系统是为了实现无偿献血规范化、有序化、高效化的管理而设计的。本文主要介绍使用java语言开发一个基于C/S架构的无偿献血管理系统&#xff0c;提高无偿献血管理的工作效率。 功能分析&#xff1a; 系统主要提供给管理员、无偿献血人员&#x…...

C语言 Number 1 基本数据类型

数据类型的定义 c语言的数据分类基本类型整型浮点型float和double的精度和范围范围精度 枚举类型空类型派生类型派生的一般表达形式 注 c语言的数据分类 首先是针对C语言的数据类型做个整理 大致分为四个大类型 基本类型枚举类型空类型派生类型 那么根据以上四个大类型 我们…...

mac录屏快捷键指南,轻松录制屏幕内容!

“大家知道mac电脑有录屏快捷键吗&#xff0c;现在录屏不太方便&#xff0c;每次都花很多时间&#xff0c;要是有录屏快捷键&#xff0c;应该会快速很多&#xff0c;可是哪里都找不到&#xff0c;有人知道吗&#xff1f;帮帮我&#xff01;” 苹果的mac电脑以其精美的设计和卓…...

精准测试是个错误

如果你已经了解了精准测试在行业的主流做法&#xff0c;你可以跳过相关内容。 行业里对于精准测试的定义 在网上流传着一些精准测试的定义&#xff08;如果你对这些定义不感冒&#xff0c;可直接跳到我个人的定义&#xff09;&#xff1a; 自网易陈逸青&#xff08;2020&#x…...

算法通关村第四关|黄金挑战|表达式问题

1.计算器问题 给定一个内容为表达式的字符串&#xff0c;计算结果。 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版是一款专门为开发人员和数据库管理员设计的免费开源通用数据库工具。软件的易用性是它的宗旨&#xff0c;是经过精心设计…...

C++ 类 根据成员变量的指针获取类对象的指针

一.宏定义 实现方式有多种&#xff0c;原理是相同的 方式1&#xff1a; #define get_class_ptr(memberPtr,classType,memberName) \ ((classType*)((char*)(memberPtr)-(unsigned long)((ULONG_PTR)&((classType*)0)->member))) 方式2&#xff1a; #define get_cl…...

图论08-图的建模-状态的表达与理解 - 倒水问题为例

文章目录 状态的表达例题1题解1 终止条件&#xff1a;有一个数位为42 状态的改变&#xff1a;a表示十位数&#xff0c;b表示个位数3 其他设置 例题2 力扣773 滑动谜题JavaC 状态的表达 例题1 从初始的(x&#xff0c;y)状态&#xff0c;到最后变成&#xff08;4&#xff0c;&am…...

sqlserver字符串拼接

本文主要介绍了sqlserver字符串拼接的实现&#xff0c;文中通过示例代码介绍的非常详细&#xff0c;对大家的学习或者工作具有一定的参考学习价值。 1. 概 在SQL语句中经常需要进行字符串拼接&#xff0c;以sqlserver&#xff0c;oracle&#xff0c;mysql三种数据库为例&#…...

MySQL-----事务

事务的概念 事务是一种机制&#xff0c;一个操作序列。包含了一组数据库的操作命令&#xff0c;所有的命令都是一个整体&#xff0c;向系统提交或者撤销的操作&#xff0c;要么都执行&#xff0c;要么都不执行。 是一个不可分割的单位 事务的ACID特点 ACID&#xff0c;是指在可…...

hive的安装配置笔记

1.上传hive安装包 2.解压 3.配置Hive(在一台机器上即可) mv hive-env.sh.template hive-env.sh 4.运行hive 发现内置默认的metastore存在问题&#xff08;1.换执行路径后&#xff0c;原来的表不存在了。2.只能有一个用户访问同一个表&#xff09; 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.…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解

进来是需要留言的&#xff0c;先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码&#xff0c;输入的<>当成字符串处理回显到页面中&#xff0c;看来只是把用户输…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...