最小生成树模板(prim,heap-prim,kruskal)
prim
出圈法,时间复杂度 O ( n 2 ) O(n^2) O(n2)
#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 5000
#define inf 100000000
struct edge{int v,w;
};
vector<edge>e[MAX_N+5];
int d[MAX_N+5],vis[MAX_N+5];
int n,m;
int ans=0,cnt=0;
bool prim(int s)
{for(int i=0;i<=n;i++)d[i]=inf;d[s]=0;for(int i=1;i<=n;i++){int u=0;for(int j=1;j<=n;j++)if(!vis[j]&&d[j]<d[u])u=j;vis[u]=1;ans+=d[u];if(d[u]!=inf)cnt++;for(auto ed:e[u]){int v=ed.v,w=ed.w;if(d[v]>w)d[v]=w;}}return n==cnt;
}
int main()
{cin>>n>>m;for(int i=1,a,b,c;i<=m;i++){scanf("%d%d%d",&a,&b,&c);e[a].push_back({b,c});e[b].push_back({a,c});}if(!prim(1)){cout<<"orz"<<endl;return 0;}else{cout<<ans<<endl;return 0;}return 0;}
heap-prim
出队法,时间复杂度 O ( m l o g m ) O(mlogm) O(mlogm)
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX_N 5000
#define inf 100000000
struct edge{int v,w;
};
vector<edge>e[MAX_N+5];
int d[MAX_N+5],vis[MAX_N+5];
int n,m;
int ans=0,cnt=0;
priority_queue<pair<int,int>>q;
bool prim(int s)
{for(int i=0;i<=n;i++)d[i]=inf;d[s]=0;q.push({0,s});while(!q.empty()){int u=q.top().second;q.pop();if(vis[u])continue;vis[u]=1;ans+=d[u];cnt++;for(auto ed:e[u]){int v=ed.v,w=ed.w;if(d[v]>w){d[v]=w;q.push({-d[v],v});}}}return n==cnt;
}
int main()
{cin>>n>>m;for(int i=1,a,b,c;i<=m;i++){scanf("%d%d%d",&a,&b,&c);e[a].push_back({b,c});e[b].push_back({a,c});}if(!prim(1)){cout<<"orz"<<endl;return 0;}else{cout<<ans<<endl;return 0;}return 0;}
kruskal
加边法,时间复杂度 O ( m l o g m ) O(mlogm) O(mlogm)
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 5000
#define MAX_M 200000
#define inf 100000000
struct edge{int u,v,w;bool operator<(const edge&t){return w<t.w;}
}e[MAX_M+5];
int k=0;
int n,m;
int fa[MAX_N+5],ans,cnt;
int find(int x)
{return fa[x]==x?x:find(fa[x]);
}
bool kruskal(){sort(e+1,e+m+1);for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){int x=find(e[i].u);int y=find(e[i].v);if(x!=y){fa[x]=y;ans+=e[i].w;cnt++;}}return cnt==n-1;
}
int main()
{cin>>n>>m;for(int i=1,a,b,c;i<=m;i++){scanf("%d%d%d",&a,&b,&c);e[++k]={a,b,c};}if(!kruskal()){cout<<"orz"<<endl;return 0;}else{cout<<ans<<endl;return 0;}return 0;}
相关文章:
最小生成树模板(prim,heap-prim,kruskal)
prim 出圈法,时间复杂度 O ( n 2 ) O(n^2) O(n2) #include<iostream> #include<vector> using namespace std; #define MAX_N 5000 #define inf 100000000 struct edge{int v,w; }; vector<edge>e[MAX_N5]; int d[MAX_N5],vis[MAX_N5]; int n,m…...
Centos 7 或 8配置国内yum源及epel源-1
官方教程 Yum工具详解 清理Yum缓存:[rootqfedu.com ~]# yum clean all缓存软件包信息: 提高搜索/安装软件的速度[rootqfedu.com ~]# yum makecache查询yum源信息: [rootqfedu.com ~]# yum repolist 查找软件:[rootqfedu.com ~]# yum search mysql 此命令会搜索到系…...
轻松解决Android复杂数据结构序列化
问题描述 当我编写quickupload库时,因为需要在 Service中进行上传任务,向Service传递时我发现需要传递的数据很多并且结构复杂,如果处理不好就会导致以下几个问题 耗时: 需要更多时间进行开发和测试以确保正确的数据处理。容易出错: 由于手…...
解析PDF文件中的图片为文本
解析PDF文件中的图片为文本 1 介绍 解析PDF文件中的图片,由两种思路,一种是自己读取PDF文件中的图片,然后用OCR解析,例如:使用PyMuPDF读取pdf文件,再用PaddleOCR或者Tesseract-OCR识别文字。另一种使用第…...
微信小程序表单
在我们的课程中,我们深入探讨了微信小程序表单的开发和应用。以下是我们课程的主要内容和收获: 一、课程目标 本课程旨在帮助学生掌握微信小程序表单的基本概念、开发流程和最佳实践。学生将学习如何创建和配置表单组件,处理表单数据…...
Javascript高级程序设计(第四版)--学习记录
var关键字:定义变量同时可以进行赋值 var message"hello" message 10 可以改变保存的值,也可以改变值的类型,但是不推荐这样写。 var声明的变量会成为包含它的函数的局部变量。 function test(){ var message "hello";…...
DVWA-CSRF-samesite分析
拿DVWA的CSRF为例子 接DVWA的分析,发现其实Impossible的PHPSESSID是设置的samesite1. 参数的意思参考Set-Cookie SameSite:控制 cookie 是否随跨站请求一起发送,这样可以在一定程度上防范跨站请求伪造攻击(CSRF)。 下面用DVWA CS…...
代码随想录训练营Day48
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、买卖股票的最佳时机4二、买卖股票的最佳时机含冷冻期三、买卖股票含手续费 前言 提示:这里可以添加本文要记录的大概内容: 今天是…...
React进阶(五):导航守卫_renderroutes
在《React进阶(四):路由介绍》博文中,介绍了React路由相关知识,在实际项目开发过程中,路由之间的跳转必定涉及权限、用户是否登陆等限定条件的判定,故需要导航守卫来完成这一事项。 在实现reac…...
Python基础系列教程:从零开始学习Python
Python有很多功能强大的机器学习和大数据分析包,适合对大数据和人工智能感兴趣的同学学习。要想了解一门语言,首先需要了解它的语法。本文将介绍Python的一些基础语法,包括数据类型、变量类型、条件控制、循环结构等内容。废话少说࿰…...
deepl翻译的PDF文档保护密码解除
1、首先将后缀名(.docx)修改为压缩包格式(.zip)。 2、修改解密word加密.py里zip的位置,和新生成的zip的位置和名称 import zipfile import xml.etree.ElementTree as ET import os import shutil# 定义文件路径 zip_file_path rC:\Users\Administrator\Desktop\新…...
LeetCode 算法:二叉树的直径 c++
原题链接🔗:二叉树的直径 难度:简单⭐️ 题目 给你一棵二叉树的根节点,返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由…...
盘立方期货Kdj幅图指标公式源码
盘立方期货Kdj幅图指标公式源码: N:250; WR1:100-100*(HHV(HIGH,N)-CLOSE)/(HHV(HIGH,N)-LLV(LOW,N)),DOT,COLORLIGHTGREEN; EW:EMA(WR1,5); STICKLINE(WR1<20,WR1,20,1,0),COLORYELLOW; STICKLINE(WR1>80,WR1,80,1,0),COLORYELLOW; RSV:(CLOSE-LLV(LOW…...
SkyWalking 极简入门
1. 概述 1.1 概念 SkyWalking 是什么? FROM Apache SkyWalking 分布式系统的应用程序性能监视工具,专为微服务、云原生架构和基于容器(Docker、K8s、Mesos)架构而设计。 提供分布式追踪、服务网格遥测分析、度量聚合和可视化一体…...
本篇内容:ArkTS开发系列之事件(2.8.1触屏、键鼠、焦点事件)
上篇回顾: ArkTS开发系列之导航 (2.7动画) 本篇内容:ArkTS开发系列之事件(2.8.1触屏、键鼠、焦点事件) 一、知识储备 1. 触屏事件:包括点击事件、拖拽事件、触摸事件。 点击事件 Button()....onClick(…...
测试的基础知识大全【测试概念、分类、模型、流程、测试用例书写、用例设计、Bug、基础功能测试实战】
测试基础笔记 Day01阶段⽬标⼀、测试介绍⼆、测试常⽤分类2.1 阶段划分单元测试集成测试系统测试验收测试 2.2 代码可⻅度划分⿊盒测试:主要针对功能(阶段划分->系统测试)灰盒测试:针对接⼝测试(阶段划分->集成测…...
Power Apps
目录 一、引言1、Power Apps2、应用场景3、Power Apps的优势与前景4、补充 二、数据源介绍1、SharePoint2、Excel3、Dataverse4、SQL5、补充(1)OneDrive 三、Power Apps应用类型1、画布应用2、模型驱动应用3、网站 Power Pages 四、Power Automate五、Po…...
qt图像处理-将OpenCV的cv::Mat类型转换为QImage类型
在使用Qt进行图像处理时,经常需要将OpenCV的cv::Mat类型转换为QImage类型。以下是几种有效的方法,可以根据具体情况选择合适的方法进行转换。 方法一:直接使用QImage构造函数 这种方法直接使用QImage的构造函数,通过传递cv::Mat的指针和相关参数来创建QImage对象。这种方…...
代码随想录训练营第十八天 530二叉搜索树的最小绝对差 501二叉搜索树中的众数 236二叉树的最近公共祖先
第一题: 原题链接:530. 二叉搜索树的最小绝对差 - 力扣(LeetCode) 思路: 使用中序遍历的方式:左中右。 定义一个pre节点来存放当前节点的前一个节点。 在中序的时候处理递归逻辑: 首先先向…...
微信小程序之横向列表展示
效果图 参考微信小程序可看 代码: <view class"lbtClass"><view class"swiper-container"><scroll-view class"swiper" scroll-x"true" :scroll-left"scrollLeft"><block v-for"(six…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
