搜索与图论——Prim算法求最小生成树

news/2024/6/20 3:27:22/文章来源:https://blog.csdn.net/2301_76553467/article/details/137156846

在最小生成树问题里,正边和负边都没问题

朴素版prim算法 时间复杂度O(n^2)

生成树:每一次选中的t点,它和集合的距离对应的那条边,就是生成树的一条边

算法流程和dijkstra算法非常相似 

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 510,INF = 0x3f3f3f3f;int n,m;
int g[N][N];
int dist[N];
bool vis[N];int prim(){memset(dist,0x3f,sizeof dist);dist[1] = 0;int res = 0;for(int i = 1; i <= n; i ++ ){int t = -1;for(int j = 1; j <= n; j ++ ){if(!vis[j] && (t == -1 || dist[j] < dist[t])){t = j;}}vis[t] = true;if(dist[t] == INF) return 0;//res的更新要先于dist[t]的更新,因为如果出现负环,就可能导致dist[t]被错误更新,从而导致res的错误res += dist[t];for(int j = 1; j <= n; j ++ ){/* 与dijkstradist[j] = min(dist[j],dist[t] + g[t][j]);不同的是,prim是与g[t][j]作比较,因为dijkstra的dist[j]表示的是j与原点的最短距离,而prim算法中dist[j]表示的是j点与集合的最短距离 */dist[j] = min(dist[j],g[t][j]);}vis[t] = true;}return res;
}int main(){cin >> n >> m;memset(g, 0x3f, sizeof g);while(m -- ){int u,v,w;cin >> u >> v >> w;//无向图是特殊的有向图,建边时只要建一条从a到b的,再建一条从b到a的就可以了g[u][v] = g[v][u] = min(g[u][v],w);}int t = prim();if(!t) cout << "impossible" << endl;else cout << t << endl;return 0;
}

堆优化版prim几乎不会用到,一般直接用kruskal就可以解决。堆优化的prim对比kruskal没有明显优势,还比较难写,故此处不贴模板。

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

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

相关文章

稀碎从零算法笔记Day33-LeetCode:生命游戏

今天是“耶稣受难人”&#xff0c;笔者给自己放了天假hhh 且慢&#xff0c;还是会写一点的。 根据 百度百科 &#xff0c; 生命游戏 &#xff0c;简称为 生命 &#xff0c;是英国数学家约翰何顿康威在 1970 年发明的细胞自动机。 题型&#xff1a;矩阵、原地实现、位运算 链…

Pytorch for training1——read data/image

blog torch.utils.data.Dataset create dataset with class torch.utils.data.Dataset automaticly import torch from torch.utils.data import Datasetclass MyDataset(Dataset):def __init__(self, data):self.data datadef __getitem__(self, index):# 根据索引获取样本…

紫光展锐P7885核心板详细参数介绍_5G安卓智能模块开发方案

紫光展锐P7885核心板采用了先进的6nm EUV制程工艺&#xff0c;集成了高性能的应用处理器和金融级安全解决方案&#xff0c;为用户带来了全新的性能体验。 P7885核心板搭载了先进的6nm制程工艺SoC P7885&#xff0c;其中包含四核A76和四核A55&#xff0c;主频可达2.7Ghz&#xf…

计算机网络面试问题(一)

1.在浏览器中输⼊URL并按下回⻋之后会发⽣什么 2.TCP三次握⼿的过程,为什么三次握手 TCP&#xff08;传输控制协议&#xff09;的三次握⼿是建⽴⽹络连接的过程&#xff0c;确保通信双⽅能够正确地进⾏数据传输。 第⼀次握⼿&#xff08;SYN&#xff09;&#xff1a; 客户端&am…

【THM】SQL Injection(SQL注入)-初级渗透测试

简介 SQL(结构化查询语言)注入,通常称为 SQLi,是对 Web 应用程序数据库服务器的攻击,导致执行恶意查询。当 Web 应用程序使用未经正确验证的用户输入与数据库进行通信时,攻击者有可能窃取、删除或更改私人数据和客户数据,并攻击 Web 应用程序身份验证方法以获取私有数据…

风险与收益

风险与收益 影响资产需求的主要因素财富总量预期收益率资产的流动性影响流动性的主要因素 风险 如何降低风险系统风险和非系统风险机会集合与有效集合资产组合理论 影响资产需求的主要因素 影响资产需求的主要因素包括&#xff1a;财富总量、预期收益率、资产的流动性和风险。…

【JavaEE初阶系列】——多线程案例四——线程池

目录 &#x1f6a9;什么是线程池 &#x1f388;从池子中取效率大于新创建线程效率(why) &#x1f6a9;标准库中的线程池 &#x1f388;为什么调用方法而不是直接创建对象 &#x1f388;工厂类里的方法 &#x1f4dd;newCachedThreadPool() &#x1f4dd;newFixedThread…

使用Leaflet.rotatedMaker进行航班飞行航向模拟的实践

目录 前言 一、Leaflet的不足 1、方向插件 2、方向控制脚本说明 二、实时航向可视化实现 1、创建主体框架 2、飞机展示 3、位置和方位模拟 三、成果及分析 1、成果展示 2、方向绑定解读 总结 前言 众所周知&#xff0c;物体在空间中的运动&#xff08;比如飞行、跑步…

【Linux】ubuntu/centos8安装zsh终端

本文首发于 ❄️慕雪的寒舍 根据这篇知乎文章进行 https://zhuanlan.zhihu.com/p/514636147 1.安装zsh 先安装zsh并设置为默认的终端 # ubuntu sudo apt install zsh # centos sudo yum install zsh util-linux-user # 通用 chsh -s /bin/zsh如果centos下找不到chsh命令&am…

深入解析实时数仓Doris:Rollup上卷表与查询

码到三十五 &#xff1a; 个人主页 心中有诗画&#xff0c;指尖舞代码&#xff0c;目光览世界&#xff0c;步履越千山&#xff0c;人间尽值得 ! 目录 一、基本概念二、Aggregate 和 Unique 模型中的 ROLLUP三、Duplicate 模型中的 ROLLUP四、ROLLUP 调整前缀索引五、ROLLUP使…

改Jenkins版本号

旧服务器迁移到新&#xff0c;打包版本号更新 Jenkins.instance.getItemByFullName("双机热备").updateNextBuildNumber(65)

154 Linux C++ 通讯架构实战9 ,信号功能添加,信号使用sa_sigaction 回调,子进程添加,文件IO详谈,守护进程添加

初始化信号 使用neg_init_signals(); 在nginx.cxx中的位置如下 //(3)一些必须事先准备好的资源&#xff0c;先初始化ngx_log_init(); //日志初始化(创建/打开日志文件)&#xff0c;这个需要配置项&#xff0c;所以必须放配置文件载入的后边&#xff1b;//(4)一些初…

【SpringBoot整合系列】SpirngBoot整合EasyExcel

目录 背景需求发展 EasyExcel官网介绍优势常用注解 SpringBoot整合EaxyExcel1.引入依赖2.实体类定义实体类代码示例注解解释 3.自定义转换器转换器代码示例涉及的枚举类型 4.Excel工具类5.简单导出接口SQL 6.简单导入接口SQL 7.复杂的导出&#xff08;合并行、合并列&#xff0…

C++刷题篇——04找等值元素

一、题目 二、解题思路 1、分割后放进二维数组 2、使用map&#xff0c;key为数值&#xff0c;value为其坐标 3、遍历二维数组元素&#xff0c;再在map中找该元素对应的value值&#xff08;二维数组形式&#xff09;&#xff0c;倘若value.size为1&#xff0c;那直接返回-1&…

每天五分钟计算机视觉:使用神经网络完成人脸的特征点检测

本文重点 我们上一节课程中学习了如何利用神经网络对图片中的对象进行定位,也就是通过输出四个参数值bx、by、bℎ和bw给出图片中对象的边界框。 本节课程我们学习特征点的检测,神经网络可以通过输出图片中对象的特征点的(x,y)坐标来实现对目标特征的识别,我们看几个例子。…

uniapp-打包IOS的APP流程

打包前所需配置 在manifest文件内配置 1. APP图标 2. 启动界面 有三种启动界面配置 第一种是 HBuilderX 官方给的通用启动界面&#xff0c;页面单一&#xff0c;屏幕中间就一个圆框图标 第二种是自定义的启动图&#xff0c;无法通过AppStore的审核 第三种是自定义storyboard启动…

蚁剑流量分析

蚁剑流量分析 在靶机上面上传一个一句话木马&#xff0c;并使用蚁剑连接&#xff0c;进行抓包, 一句话木马内容 <?php eval($_POST[1]); defalut编码器 在使用蚁剑连接的时候使用default编码器 连接之后进行的操作行为是查看当前目录(/var/www/html)下的文件&#xff0…

MySQL-主从复制与读写分离

一、MySQL主从复制&#xff1a; 1、主从复制的作用&#xff1a; 主从复制&#xff1a;主设备通过二进制日志传输到从设备&#xff0c;从设备通过二进制日志和主同步数据。 作用&#xff1a;负载均衡读操作&#xff0c;备份(实时备份&#xff0c;不能替换手动的备份)&#xf…

(QT5142、OpenCV452、SeetaFace2 )facetest

服务端 .pro QT core gui network sql#window平台opencv&#xff0c;seetaface环境 win32{ LIBS C:\opencv452\x64\mingw\lib\libopencv* LIBS C:\SeetaFace\lib\libSeeta* INCLUDEPATH C:\opencv452\include INCLUDEPATH C:\opencv452\include\opencv2 INCLUDEPATH …

技术分享 | 如何写好测试用例?

对于软件测试工程师来说&#xff0c;设计测试用例和提交缺陷报告是最基本的职业技能。是非常重要的部分。一个好的测试用例能够指示测试人员如何对软件进行测试。在这篇文章中&#xff0c;我们将介绍测试用例设计常用的几种方法&#xff0c;以及如何编写高效的测试用例。 ## 一…