acwing算法基础之搜索与图论--kruskal算法
目录
- 1 基础知识
- 2 模板
- 3 工程化
1 基础知识
kruskal算法的关键步骤为:
- 将所有边按照权重从小到大排序。
- 定义集合S,表示生成树。
- 枚举每条边(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算法的关键步骤为: 将所有边按照权重从小到大排序。定义集合S,表示生成树。枚举每条边(a,b,c),起点a,终点b,边长c。如果结点a和结点b不连通(用并查集来…...
微信H5跳转微信小程序
官方文档:目录 | 微信开放文档 方法一:微信浏览器打开的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 …...
设计模式是测试模式咩?
设计模式和测试模式概述 软件的生命周期为什么要进行测试(测试的目的)?软件的设计模式1. **瀑布模型**3. 增量和迭代模型4. 敏捷模型5. 喷泉模型 测试模型V模型W模型 一个应用程序从出生到“死亡”会经过非常漫长的流程…… 软件的生命周期 …...
Aspose.OCR for .NET 2023Crack
Aspose.OCR for .NET 2023Crack 为.NET在图片上播放OCR使所有用户和程序员都可以从特定的图像片段中提取文本和相关的细节,如字体、设计以及书写位置。这一特定属性为OCR的性能及其在扫描遵循排列的记录时的功能提供了动力。OCR的库使用一条线甚至几条线来处理这些特…...
conda环境中pytorch1.2.0版本安装包安装一直失败解决办法!!!
conda环境中pytorch1.2.0版本安装包安装一直失败解决办法 cuda10.0以及cudnn7.4现在以及安装完成,就差torch的安装了,现在torch我要装的是1.2.0版本的,安装包以及下载好了,安装包都是在这个网站里下载的(点此进入&…...
后端面试问题(学习版)
JAVA相关 JAVA语言概述 1. 一个".java"源文件中是否可以包含多个类?有什么限制? 可以。 一个源文件可以声明多个类,但是最多只能有一个类使用public进行声明 且要求声明public的类的类名与源文件相同。 2. Java的优势ÿ…...
数据管理系统-week1-介绍
文章目录 一、数据它是什么?二、电子存储设备三、持久存储设备1、硬盘驱动器(HDD)、硬盘、硬盘驱动器是一种用于存储和检索数字信息的机电持久存储设备。2、固态硬盘(SSD)使用非易失性存储器,即使用NAND闪存…...
【SpringBoot】手写模拟SpringBoot核心流程
依赖包 新建一个工程,包含两个 module: springboot 模块,表示 springboot 源码实现;user 模块,表示业务系统,使用 springboot 模块; 依赖包:Spring、SpringMVC、Tomcat 等ÿ…...
应对.locked勒索病毒:恢复、预防全方位攻略
导言: .locked勒索病毒并非简单的数字威胁,它是一场对个人和企业数字资产的精密审判。这种病毒通过各种方式感染系统,从而以瞬间之间将用户的关键文件变成数字拼图,无情地要求赎金以换取解锁的密钥。如果您正在经历勒索病毒数据恢…...
基于DS1302时钟液晶12864显示2路闹钟仿真及源程序
一、系统方案 1、本设计采用51单片机作为主控器。 2、DS1302采集年月日时分秒送到液晶12864显示。 3、按键年月日时分秒,两路闹钟。 二、硬件设计 原理图如下: 三、单片机软件设计 1、首先是系统初始化 uchar clock_time[6] {0X00,0X59,0X23,0X09,0X…...
AGC034E Complete Compress
AGC034E Complete Compress 洛谷[AGC034E] Complete Compress 题目大意 给你一棵有 n n n个节点的树,并用 01 01 01串告诉你哪些节点上有棋子(恰好一棵)。 你可以进行若干次操作,每次操作可以将两颗距离至少为 2 2 2的棋子向彼…...
python设计模式12:状态模式
什么是状态机? 关键属性: 状态和转换 状态: 系统当前状态 转换:一种状态到另外一种状态的变化。 转换由触发事件或是条件启动。 状态机-状态图 状态机使用场景: 自动售货机 电梯 交通灯 组合锁 停车计时…...
JS对图片尺寸和DPI进行编辑修改(1寸照修改为2寸照)
各种报名都对照片有大小限制,鉴于这种情况,网上搜了后拼凑出了如下代码,用于解决1寸照片修改为2寸照片,同时将DPI修改为300,当然也可以根据自己的情况修改代码: HTML <input type"file" id&…...
EDA实验----四选一多路选择器设计(QuartusII)
目录 一.实验目的 二.实验仪器设备 三.实验原理: 四.实验要求 五.实验内容及步骤 1.实验内容 2.实验步骤 六.实验报告 七.实验过程 1.创建Verilog文件,写代码 2.波形仿真 …...
从windows iso文件中提取install.wim
1、首先从微软官方下载需要的windows镜像 https://www.microsoft.com/zh-cn/software-download/windows10/ 2、在下载的iso文件右键,打开压缩包,在sources文件夹下,应该就可以看到install.wim了。但似乎在最新的win10版本,微软采…...
Python的flask网页编程的GET和POST方法的区别
关于flask网页编程的GET及POST方法之间存在哪些区别问题,我们主要从以下六个关键点予以详细阐述: 首先需要明确的是,GET与POST两种不同类型的HTTP方法所采用的请求模式有所差别。其中,GET方法采用的是基于URL请求的机制ÿ…...
15 # 手写 throttle 节流方法
什么是节流 节流是限制事件触发的频率,当持续触发事件时,在一定时间内只执行一次事件,这个效果跟英雄联盟里的闪现技能释放差不多。 函数防抖关注一定时间连续触发的事件只在最后执行一次,而函数节流侧重于一段时间内只执行一次…...
puzzle(1612)拼单词、wordlegame
目录 拼单词 wordlegame 拼单词 在线play 找出尽可能多的单词。 如果相邻的话(在任何方向上),你可以拖拽鼠标从一个字母(方格)到另一个字母(方格)。在一个单词中,你不能多次使用…...
【解决方案】pytion 运行时提示 import psutil ModuleNotFoundError: No module named ‘psutil‘
报错原因分析 import psutil ModuleNotFoundError: No module named psutil报错原因分析 当前环境pytion中缺少了psutil包,使用pip命令进行安装 解决方案 pip install psutil...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
离线语音识别方案分析
随着人工智能技术的不断发展,语音识别技术也得到了广泛的应用,从智能家居到车载系统,语音识别正在改变我们与设备的交互方式。尤其是离线语音识别,由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力,广…...
