2023-9-2 Kruskal算法求最小生成树

题目链接:Kruskal算法求最小生成树

在这里插入图片描述

#include <iostream>
#include <algorithm>using namespace std;const int N = 200010;// 与并查集中的p含义相同
int p[N];struct Edge
{int a, b, w;bool operator< (const Edge & W)const{return w < W.w;}
}edges[N];int n, m;int find(int a)
{if(p[a] != a) p[a] = find(p[a]);return p[a];
}int main()
{cin >> n >> m;for(int i = 0; i < m; i ++){int a, b, c;cin >> a >> b >> c;edges[i] = {a, b, c};}sort(edges, edges + m);// 初始化for(int i = 1; i <= n; i ++) p[i] = i;int res = 0, cnt = 0;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){p[a] = b;res += w;cnt ++;}}if(cnt < n - 1) cout << "impossible" << endl;else cout << res << endl;return 0;
}

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

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

相关文章

浅析Linux SCSI子系统:错误恢复

文章目录 概述SCSI错误恢复处理添加错误恢复命令错误恢复线程scsi_eh_ready_devs IO超时处理相关参考 概述 IO路径是一个漫长的过程&#xff0c;从SCSI命令请求下发到请求完成返回&#xff0c;中间的任何一个环节出现问题都会导致IO请求的失败。从SCSI子系统到低层驱动&#x…

【快手小玩法-弹幕游戏】开发者功能测试报告提交模板

背景 快手有明确的要求&#xff0c;准入和准出更加严格&#xff0c;要求有明确的测试报告。格式如下&#xff1a; *本文参考字节wiki&#xff1a;CP侧测试报告模板(复制填写轻雀文档) 其他文章推荐&#xff1a;【抖音小玩法-弹幕游戏】开发者功能测试报告提交模板 一、前言…

Java后端开发面试题——集合篇

ArrayList底层的实现原理是什么 底层数据结构 ArrayList底层是用动态的数组实现的 初始容量 ArrayList初始容量为0&#xff0c;当第一次添加数据的时候才会初始化容量为10 扩容逻辑 ArrayList在进行扩容的时候是原来容量的1.5倍&#xff0c;每次扩容都需要拷贝数组 添加逻…

MMSegmentation训练自己的语义分割数据集

全流程&#xff0c;训练语义分割数据集 数据标注json转mask 运行源码MMSegmentation模型选择运行部分 数据标注 # 安装 pip install labelme # 启动labelme labelme然后 ctrl N 开启多边形标注即可&#xff0c;命名类为person 之后会保存到同目录下json文件&#xff1a; js…

WordPress(6)网站侧边栏倒计时进度小工具

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 效果图在这里插入图片描述一、添加位置二、主题style.css文件中添加美化1.引入库2.添加自定义的HTML模块效果图 提示:以下是本篇文章正文内容,下面案例可供参考 一、添加位置 在主题中 child.js…

【1++的数据结构】之AVL树

&#x1f44d;作者主页&#xff1a;进击的1 &#x1f929; 专栏链接&#xff1a;【1的数据结构】 文章目录 一&#xff0c;什么是AVL树二&#xff0c;AVL树的插入三&#xff0c;AVL树的旋转3.1 向左旋转3.2 向右旋转3.3 左右双旋3.4 右左双旋 四&#xff0c;验证AVL树是否平衡 …

Data truncation: Out of range value for column ‘id‘ at row 1

错误信息&#xff1a;Data truncation: Out of range value for column id at row 1 数据截断&#xff1a;第1行“id”列的值超出范围 很多人会回复&#xff1a;数据库 类型由int改为 bigInt 我看了表结构 可以放的下的。 是 bigint(20) 没有问题啊。 默认的 bigint 类型…

C语言面试题值反转字符串

知识捡漏本 1.C语言优先级 &#xff1a;左高于高于 右 2.定义宏函数product&#xff0c;调用product后&#xff0c;里面的i和i都是加两次1&#xff0c;i就是两个加2后的i相乘&#xff0c;i是开始的i和1后的i相乘。 3.用i (j4,k 8,m 16);这种定义方法&#xff0c;最终i和最后一…

dji uav建图导航系列()ROS中创建dji_sdk节点包(一)项目结构

文章目录 1、整体项目结构1.1、 目录launch1.2、文件CMakeLists.txt1.3、文件package.xml1.4、目录include1.4、目录srv在ROS框架下创建一个无人机的节点dji_sdk,实现必需的订阅(控制指令)、发布(无人机里程计)、服务(无人机起飞降落、控制权得很)功能,就能实现一个类似…

全球免费编程教育网站:Code.org

全球免费编程教育网站&#xff1a;Code.org 官网地址注册使用 你还在为小朋友的编程教育而发愁吗&#xff1f; 你还在为小朋友放假无聊而头疼吗&#xff1f; 他来了他来了&#xff0c;全球免费编程教育网站来了。 2013年成立的Code.org是一个非营利组织。 它致力于为年轻女子、…

【RISC-V】RISC-V寄存器

一、通用寄存器 32位RISC-V体系结构提供32个32位的整型通用寄存器寄存器别名全称说明X0zero零寄存器可做源寄存器(rs)或目标寄存器(rd)X1ra链接寄存器保存函数返回地址X2sp栈指针寄存器指向栈的地址X3gp全局寄存器用于链接器松弛优化X4tp线程寄存器常用于在OS中保存指向进程控…

Qt/C++编写视频监控系统81-Onvif报警抓图和录像并回放

一、前言 视频监控系统中的图文警情模块&#xff0c;是通过Onvif协议的事件订阅拿到的&#xff0c;通过事件订阅后&#xff0c;设备的各种报警事件比如入侵报警/遮挡报警/越界报警/开关量报警等&#xff0c;触发后都会主动往订阅者发送&#xff0c;而且一般都是会发送两次&…

Node.js crypto模块 加密算法

背景 微信小程序调用飞蛾热敏纸打印机&#xff0c;需要进行参数sig签名校验&#xff0c;使用的是sha1进行加密 // 通过crypto.createHash()函数&#xff0c;创建一个hash实例&#xff0c;但是需要调用md5&#xff0c;sha1&#xff0c;sha256&#xff0c;sha512算法来实现实例的…

企业架构LNMP学习笔记7

PHP介绍&#xff1a; HTML&#xff1a;超文本标记语言 http: 超文本传输协议 端口80 浏览器将html代码解析成web页面。 PHP&#xff1a;超文本预处理器。后端语言开发&#xff0c;页面上需要动态改变修改的&#xff0c;需要连接数据库查询数据&#xff0c;转为html。 主要…

流媒体弱网优化之路(BBR应用)——GCC与BBR的算法思想分析

流媒体弱网优化之路(WebRTC)——GCC与BBR的算法思想分析 —— 我正在的github给大家开发一个用于做实验的项目 —— github.com/qw225967/Bifrost目标&#xff1a;可以让大家熟悉各类Qos能力、带宽估计能力&#xff0c;提供每个环节关键参数调节接口并实现一个json全配置&…

WebSocket(一)

一.什么是WebSocket 【1】WebSocket是一种协议&#xff0c;设计用于提供低延迟&#xff0c;全双工和长期运行的连接。 全双工&#xff1a;通信的两个参与方可以同时发送和接收数据&#xff0c;不需要等待对方的响应或传输完成。 【2】比较 传统通信&#xff08;http协议&am…

Docker 的快速使用

ubuntu安装 centos安装 安装完毕之后执行一下这条命令&#xff0c;可以避免每次使用docker命令都需要sudo权限 sudo usermod -aG docker $USER阿里云docker镜像加速 DockerHub 遇到不懂或者不会使用的命令可以使用docker --help查看文档 docker --help 如&#xff1a; dock…

JavaWeb 文件上传和下载

目录 一、文件上传 1.文件上传和下载的使用说明 : 2.文件上传基本原理 : 3.文件上传经典案例 : 3.1 页面实现: 3.2 servlet实现 : 3.3 工具类实现 : 3.4 运行测试 : 3.5 注意事项 : 二、文件下载 1.文件下载基本原理 : 2.文件下载经典案例 : 2.1 准备工作 2.2 页面…

关于C语言参数传递的

一、C语言参数传递是整体带入 #include <stdio.h> #define DF(a,b) (a2*b) int main() { int s5; int k DF((s1),(s-3)); printf("%d",k); }输出结果 原因&#xff1a; #define DF(a,b) (a2*b) int k DF((s1),(s-3)); //等效 int k DF((s1)2 * (s-3)); …

useEffect 不可忽视的 cleanup 函数

在 react 开发中&#xff0c; useEffect 是我们经常会使用到的钩子&#xff0c;一个基础的例子如下&#xff1a; useEffect(() > {// some code here// cleanup 函数return () > {doSomething()} }, [dependencies])上述代码中&#xff0c; cleanup 函数的执行时机有如下…