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

acwing算法基础之搜索与图论--kruskal算法

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

kruskal算法的关键步骤为:

  1. 将所有边按照权重从小到大排序。
  2. 定义集合S,表示生成树。
  3. 枚举每条边(a,b,c),起点a,终点b,边长c。如果结点a和结点b不连通(用并查集来维护),则将这条边加入到集合S中。

kruskal算法的时间复杂度为O(mlogm),它用来解决稀疏图的最小生成树问题。

2 模板

int n, m;       // 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()
{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) return INF;return res;
}

3 工程化

题目1:求最小生成树。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 2e5 + 10;
int p[N];
int n, m;struct Edge {int a, b, w;bool operator< (const Edge& W) const {return w < W.w;}
}edges[N];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {cin >> n >> m;for (int i = 0; i < m; ++i) {cin >> edges[i].a >> edges[i].b >> edges[i].w;}//初始化并查集for (int i = 1; i <= n; ++i) p[i] = i;sort(edges, edges + m);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;
}

相关文章:

acwing算法基础之搜索与图论--kruskal算法

目录 1 基础知识2 模板3 工程化 1 基础知识 kruskal算法的关键步骤为&#xff1a; 将所有边按照权重从小到大排序。定义集合S&#xff0c;表示生成树。枚举每条边(a,b,c)&#xff0c;起点a&#xff0c;终点b&#xff0c;边长c。如果结点a和结点b不连通&#xff08;用并查集来…...

微信H5跳转微信小程序

官方文档&#xff1a;目录 | 微信开放文档 方法一&#xff1a;微信浏览器打开的h5跳转方式 HTML代码 <wx-open-launch-weapp id"launch-btn" username"所需跳转的小程序原始id" path"pages/pay/pay"><script type"text/wxtag…...

Yii2 引入 外部无命名空间的类,Class not found

记一次问题解决 问题描述 支付宝开放平台SDK v2 无命名空间。需 require 引入。 require Yii::$app->vendorPath."/alipay-sdk-php/v2/aop/AopClient.php"; var_dump(new AopClient([]));exit();上述写法会直接报错。 Class temporary\controllers\AopClient …...

设计模式是测试模式咩?

设计模式和测试模式概述 软件的生命周期为什么要进行测试&#xff08;测试的目的&#xff09;&#xff1f;软件的设计模式1. **瀑布模型**3. 增量和迭代模型4. 敏捷模型5. 喷泉模型 测试模型V模型W模型 一个应用程序从出生到“死亡”会经过非常漫长的流程…… 软件的生命周期 …...

Aspose.OCR for .NET 2023Crack

Aspose.OCR for .NET 2023Crack 为.NET在图片上播放OCR使所有用户和程序员都可以从特定的图像片段中提取文本和相关的细节&#xff0c;如字体、设计以及书写位置。这一特定属性为OCR的性能及其在扫描遵循排列的记录时的功能提供了动力。OCR的库使用一条线甚至几条线来处理这些特…...

conda环境中pytorch1.2.0版本安装包安装一直失败解决办法!!!

conda环境中pytorch1.2.0版本安装包安装一直失败解决办法 cuda10.0以及cudnn7.4现在以及安装完成&#xff0c;就差torch的安装了&#xff0c;现在torch我要装的是1.2.0版本的&#xff0c;安装包以及下载好了&#xff0c;安装包都是在这个网站里下载的&#xff08;点此进入&…...

后端面试问题(学习版)

JAVA相关 JAVA语言概述 1. 一个".java"源文件中是否可以包含多个类&#xff1f;有什么限制&#xff1f; 可以。 一个源文件可以声明多个类&#xff0c;但是最多只能有一个类使用public进行声明 且要求声明public的类的类名与源文件相同。 2. Java的优势&#xff…...

数据管理系统-week1-介绍

文章目录 一、数据它是什么&#xff1f;二、电子存储设备三、持久存储设备1、硬盘驱动器&#xff08;HDD&#xff09;、硬盘、硬盘驱动器是一种用于存储和检索数字信息的机电持久存储设备。2、固态硬盘&#xff08;SSD&#xff09;使用非易失性存储器&#xff0c;即使用NAND闪存…...

【SpringBoot】手写模拟SpringBoot核心流程

依赖包 新建一个工程&#xff0c;包含两个 module&#xff1a; springboot 模块&#xff0c;表示 springboot 源码实现&#xff1b;user 模块&#xff0c;表示业务系统&#xff0c;使用 springboot 模块&#xff1b; 依赖包&#xff1a;Spring、SpringMVC、Tomcat 等&#xff…...

应对.locked勒索病毒:恢复、预防全方位攻略

导言&#xff1a; .locked勒索病毒并非简单的数字威胁&#xff0c;它是一场对个人和企业数字资产的精密审判。这种病毒通过各种方式感染系统&#xff0c;从而以瞬间之间将用户的关键文件变成数字拼图&#xff0c;无情地要求赎金以换取解锁的密钥。如果您正在经历勒索病毒数据恢…...

基于DS1302时钟液晶12864显示2路闹钟仿真及源程序

一、系统方案 1、本设计采用51单片机作为主控器。 2、DS1302采集年月日时分秒送到液晶12864显示。 3、按键年月日时分秒&#xff0c;两路闹钟。 二、硬件设计 原理图如下&#xff1a; 三、单片机软件设计 1、首先是系统初始化 uchar clock_time[6] {0X00,0X59,0X23,0X09,0X…...

AGC034E Complete Compress

AGC034E Complete Compress 洛谷[AGC034E] Complete Compress 题目大意 给你一棵有 n n n个节点的树&#xff0c;并用 01 01 01串告诉你哪些节点上有棋子&#xff08;恰好一棵&#xff09;。 你可以进行若干次操作&#xff0c;每次操作可以将两颗距离至少为 2 2 2的棋子向彼…...

python设计模式12:状态模式

什么是状态机&#xff1f; 关键属性&#xff1a; 状态和转换 状态&#xff1a; 系统当前状态 转换&#xff1a;一种状态到另外一种状态的变化。 转换由触发事件或是条件启动。 状态机-状态图 状态机使用场景&#xff1a; 自动售货机 电梯 交通灯 组合锁 停车计时…...

JS对图片尺寸和DPI进行编辑修改(1寸照修改为2寸照)

各种报名都对照片有大小限制&#xff0c;鉴于这种情况&#xff0c;网上搜了后拼凑出了如下代码&#xff0c;用于解决1寸照片修改为2寸照片&#xff0c;同时将DPI修改为300&#xff0c;当然也可以根据自己的情况修改代码&#xff1a; HTML <input type"file" id&…...

EDA实验----四选一多路选择器设计(QuartusII)

目录 一&#xff0e;实验目的 二&#xff0e;实验仪器设备 三&#xff0e;实验原理&#xff1a; 四&#xff0e;实验要求 五&#xff0e;实验内容及步骤 1.实验内容 2.实验步骤 六&#xff0e;实验报告 七.实验过程 1.创建Verilog文件&#xff0c;写代码 2.波形仿真 …...

从windows iso文件中提取install.wim

1、首先从微软官方下载需要的windows镜像 https://www.microsoft.com/zh-cn/software-download/windows10/ 2、在下载的iso文件右键&#xff0c;打开压缩包&#xff0c;在sources文件夹下&#xff0c;应该就可以看到install.wim了。但似乎在最新的win10版本&#xff0c;微软采…...

Python的flask网页编程的GET和POST方法的区别

关于flask网页编程的GET及POST方法之间存在哪些区别问题&#xff0c;我们主要从以下六个关键点予以详细阐述&#xff1a; 首先需要明确的是&#xff0c;GET与POST两种不同类型的HTTP方法所采用的请求模式有所差别。其中&#xff0c;GET方法采用的是基于URL请求的机制&#xff…...

15 # 手写 throttle 节流方法

什么是节流 节流是限制事件触发的频率&#xff0c;当持续触发事件时&#xff0c;在一定时间内只执行一次事件&#xff0c;这个效果跟英雄联盟里的闪现技能释放差不多。 函数防抖关注一定时间连续触发的事件只在最后执行一次&#xff0c;而函数节流侧重于一段时间内只执行一次…...

puzzle(1612)拼单词、wordlegame

目录 拼单词 wordlegame 拼单词 在线play 找出尽可能多的单词。 如果相邻的话&#xff08;在任何方向上&#xff09;&#xff0c;你可以拖拽鼠标从一个字母&#xff08;方格&#xff09;到另一个字母&#xff08;方格&#xff09;。在一个单词中&#xff0c;你不能多次使用…...

【解决方案】pytion 运行时提示 import psutil ModuleNotFoundError: No module named ‘psutil‘

报错原因分析 import psutil ModuleNotFoundError: No module named psutil报错原因分析 当前环境pytion中缺少了psutil包&#xff0c;使用pip命令进行安装 解决方案 pip install psutil...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...