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

最小生成树模板(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 出圈法&#xff0c;时间复杂度 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库时&#xff0c;因为需要在 Service中进行上传任务&#xff0c;向Service传递时我发现需要传递的数据很多并且结构复杂&#xff0c;如果处理不好就会导致以下几个问题 耗时: 需要更多时间进行开发和测试以确保正确的数据处理。容易出错: 由于手…...

解析PDF文件中的图片为文本

解析PDF文件中的图片为文本 1 介绍 解析PDF文件中的图片&#xff0c;由两种思路&#xff0c;一种是自己读取PDF文件中的图片&#xff0c;然后用OCR解析&#xff0c;例如&#xff1a;使用PyMuPDF读取pdf文件&#xff0c;再用PaddleOCR或者Tesseract-OCR识别文字。另一种使用第…...

微信小程序表单

在我们的课程中&#xff0c;我们深入探讨了微信小程序表单的开发和应用。以下是我们课程的主要内容和收获&#xff1a; 一、课程目标 本课程旨在帮助学生掌握微信小程序表单的基本概念、开发流程和最佳实践。学生将学习如何创建和配置表单组件&#xff0c;处理表单数据&#xf…...

Javascript高级程序设计(第四版)--学习记录

var关键字&#xff1a;定义变量同时可以进行赋值 var message"hello" message 10 可以改变保存的值&#xff0c;也可以改变值的类型&#xff0c;但是不推荐这样写。 var声明的变量会成为包含它的函数的局部变量。 function test(){ var message "hello";…...

DVWA-CSRF-samesite分析

拿DVWA的CSRF为例子 接DVWA的分析&#xff0c;发现其实Impossible的PHPSESSID是设置的samesite1. 参数的意思参考Set-Cookie SameSite:控制 cookie 是否随跨站请求一起发送&#xff0c;这样可以在一定程度上防范跨站请求伪造攻击&#xff08;CSRF&#xff09;。 下面用DVWA CS…...

代码随想录训练营Day48

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、买卖股票的最佳时机4二、买卖股票的最佳时机含冷冻期三、买卖股票含手续费 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 今天是…...

React进阶(五):导航守卫_renderroutes

在《React进阶&#xff08;四&#xff09;&#xff1a;路由介绍》博文中&#xff0c;介绍了React路由相关知识&#xff0c;在实际项目开发过程中&#xff0c;路由之间的跳转必定涉及权限、用户是否登陆等限定条件的判定&#xff0c;故需要导航守卫来完成这一事项。 在实现reac…...

Python基础系列教程:从零开始学习Python

Python有很多功能强大的机器学习和大数据分析包&#xff0c;适合对大数据和人工智能感兴趣的同学学习。要想了解一门语言&#xff0c;首先需要了解它的语法。本文将介绍Python的一些基础语法&#xff0c;包括数据类型、变量类型、条件控制、循环结构等内容。废话少说&#xff0…...

deepl翻译的PDF文档保护密码解除

1、首先将后缀名(.docx)修改为压缩包格式(.zip)。 2、修改解密word加密.py里zip的位置&#xff0c;和新生成的zip的位置和名称 import zipfile import xml.etree.ElementTree as ET import os import shutil# 定义文件路径 zip_file_path rC:\Users\Administrator\Desktop\新…...

LeetCode 算法:二叉树的直径 c++

原题链接&#x1f517;&#xff1a;二叉树的直径 难度&#xff1a;简单⭐️ 题目 给你一棵二叉树的根节点&#xff0c;返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由…...

盘立方期货Kdj幅图指标公式源码

盘立方期货Kdj幅图指标公式源码&#xff1a; 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 是什么&#xff1f; FROM Apache SkyWalking 分布式系统的应用程序性能监视工具&#xff0c;专为微服务、云原生架构和基于容器&#xff08;Docker、K8s、Mesos&#xff09;架构而设计。 提供分布式追踪、服务网格遥测分析、度量聚合和可视化一体…...

本篇内容:ArkTS开发系列之事件(2.8.1触屏、键鼠、焦点事件)

上篇回顾&#xff1a; ArkTS开发系列之导航 (2.7动画&#xff09; 本篇内容&#xff1a;ArkTS开发系列之事件&#xff08;2.8.1触屏、键鼠、焦点事件&#xff09; 一、知识储备 1. 触屏事件&#xff1a;包括点击事件、拖拽事件、触摸事件。 点击事件 Button()....onClick(…...

测试的基础知识大全【测试概念、分类、模型、流程、测试用例书写、用例设计、Bug、基础功能测试实战】

测试基础笔记 Day01阶段⽬标⼀、测试介绍⼆、测试常⽤分类2.1 阶段划分单元测试集成测试系统测试验收测试 2.2 代码可⻅度划分⿊盒测试&#xff1a;主要针对功能&#xff08;阶段划分->系统测试&#xff09;灰盒测试&#xff1a;针对接⼝测试&#xff08;阶段划分->集成测…...

Power Apps

目录 一、引言1、Power Apps2、应用场景3、Power Apps的优势与前景4、补充 二、数据源介绍1、SharePoint2、Excel3、Dataverse4、SQL5、补充&#xff08;1&#xff09;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二叉树的最近公共祖先

第一题&#xff1a; 原题链接&#xff1a;530. 二叉搜索树的最小绝对差 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 使用中序遍历的方式&#xff1a;左中右。 定义一个pre节点来存放当前节点的前一个节点。 在中序的时候处理递归逻辑&#xff1a; 首先先向…...

微信小程序之横向列表展示

效果图 参考微信小程序可看 代码&#xff1a; <view class"lbtClass"><view class"swiper-container"><scroll-view class"swiper" scroll-x"true" :scroll-left"scrollLeft"><block v-for"(six…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...