堆优化版本的Prim

  • prim和dijkstra每轮找最小边的松弛操作其实是同源的,因而受dijkstra堆优化的启发,那么prim也可以采用小根堆进行优化。
  • 时间复杂度也由 O ( n 2 ) O(n^2) O(n2)降为 O ( n l o g n ) O(nlogn) O(nlogn)

测试一下吧:原题链接

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef int VertexType;
typedef int Info;
typedef pair<int,int> PII;const int N = 110;// 书面形式的邻接表
typedef struct ArcNode{int adjvex;Info weight;struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode{VertexType data;        // 这里  结点编号就是结点表的下标  一一映射ArcNode* firstarc;
}VNode, AdjList[N];
typedef struct ALGraph{AdjList vertices;int vexnum, arcnum;ALGraph(){for(int i = 0;i < N;i ++)         vertices[i].firstarc = nullptr;}
}ALGraph;int prim_with_heap(ALGraph& G){int sum = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;int dist[N];bool st[N];memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[1] = 0;heap.push({0, 1});while(heap.size()){PII t = heap.top();heap.pop();int vex = t.second, distance = t.first;if(st[vex])     continue;st[vex] = true;sum += distance;for(ArcNode* parc = G.vertices[vex].firstarc;parc;parc = parc -> nextarc)if((parc -> weight) < dist[parc -> adjvex]){dist[parc -> adjvex] = parc -> weight;heap.push({parc -> weight, parc -> adjvex});}}return sum;
}void add(ALGraph& G, VertexType a, VertexType b, Info w){   // a -> bVNode* u = &G.vertices[a];ArcNode* newarc = new ArcNode;newarc -> adjvex = b;newarc -> weight = w;newarc -> nextarc = u -> firstarc;u -> firstarc = newarc;     // 头插法G.arcnum ++;
}int main(){ALGraph g;cin >> g.vexnum;for(int i = 1;i <= g.vexnum;i ++)for(int j = 1;j <= g.vexnum;j ++){int w;cin >> w;add(g, i, j, w);}int sum = prim_with_heap(g);cout << sum << endl;return 0;
}

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

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

相关文章

UVM 验证方法学之interface学习系列文章(七)高级 《bind 操作》(4)级联

在 SystemVerilog 中,bind 操作符用于将一个模块或接口实例绑定到另一个模块或接口的层次结构中。这在很多情况下非常有用,尤其是当你需要在不修改原始模块代码的情况下,添加或替换某些组件时。bind 操作符常用于仿真和测试平台中,以便灵活地组织测试环境。 前面的文章,我…

Vue3+SpringBoot3+Sa-Token+Redis+mysql8通用权限系统

sa-token支持分布式token 前后端代码&#xff0c;地球号: bright12389

Ansys Zemax Optical Studio 中的近视眼及矫正

近视&#xff0c;通常称为近视眼&#xff0c;是一种眼睛屈光不正&#xff0c;导致远处物体模糊&#xff0c;而近处物体清晰。这是一种常见的视力问题&#xff0c;通常发生在眼球过长或角膜&#xff08;眼睛前部清晰的部分&#xff09;过于弯曲时。因此&#xff0c;进入眼睛的光…

利用FileZilla搭建ftp服务器

一 利用windows自带的ftp服务搭建服务器&#xff0c;要复杂一些&#xff0c;好处是无需借用外部软件。 也有一些好的工具&#xff0c;如FileZilla的Server版&#xff0c;构建过程简单&#xff0c;好用。 下面看看。 二 安装FileZilla Server 当前下载版本是0.9.43&#xf…

2022 年中高职组“网络安全”赛项-海南省省竞赛任务书-1-B模块B-1-Windows操作系统渗透测试

前言 本章节我将带领大家一起重新模拟操作一次Windows渗透测试模块&#xff0c;并加固的流程。 任务概览 环境部署 我的实验复现环境&#xff1a; 服务器Windows server 2008 R2 攻击机Kali Linux 场景操作系统Windows 7 额外还有台交换机支持&#xff1a; 这里我使用的是…

【滑动窗口】变种题目:leetcode76:最小覆盖子串

前言 滑动窗口是算法的数组部分中非常重要的一个内容&#xff0c;关于滑动窗口的题目&#xff0c;我已经发布过相关的变种题目文章&#xff0c;链接如下&#xff0c;欢迎访问&#xff1a; 【滑动窗口】相关题目分析讲解:leetcode209,leetcode904 如果你不了解什么是滑动窗口&a…

蚁群算法(Ant Colony Optimization, ACO)

简介 蚁群算法&#xff08;Ant Colony Optimization, ACO&#xff09;是一种基于自然启发的优化算法&#xff0c;由意大利学者马可多里戈&#xff08;Marco Dorigo&#xff09;在1992年首次提出。它受自然界中蚂蚁觅食行为的启发&#xff0c;用于解决离散优化问题。 在自然界…

1-测试go-redis缓存数据

1-测试go-redis缓存数据 1.go-redis缓存数据测试效果 a.测试页面 测试页面&#xff1a;--这里使用 Postman 来做测试 http://127.0.0.1:8000/article/getone/3 http://127.0.0.1:8000/article/getone/4 http://127.0.0.1:8000/article/getone/5b.测试效果 查看终端&#xf…

计算机毕业设计SparkStreaming+Kafka图书推荐系统 豆瓣图书数据分析可视化大屏 豆瓣图书爬虫 知识图谱 图书大数据 大数据毕业设计 机器学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

字符串的常用函数

目录 一、引入 二、13个字符串的常用函数 总结 一、引入 在C语言中&#xff0c;字符串被视为字符数组的序列&#xff0c;以空字符\0结尾。这个空字符不是数字0&#xff0c;而是一个特殊的控制字符&#xff0c;用于标记字符串的结束。例如&#xff0c;声明char name[7] {R,…

丹摩|重返丹摩(下)

目录 四.模型构建与训练 1.模型选择 (1). 机器学习模型 (2). 深度学习模型 (3). AutoML 功能 2.参数配置 (1). 模型参数 (2). 数据划分 (3). 超参数优化 3.模型训练与评估 (1). 训练模型 (2). 查看训练结果 (3). 模型评估 五.模型部署与应用 1.模型部署 (1). 直…

浪潮信息自动驾驶框架AutoDRRT 2.0,赋能高阶自动驾驶

随着自动驾驶技术的迅猛进步&#xff0c;BEVTransformer的感知模式为高阶自动驾驶带来了前所未有的精度、泛化能力和多模态融合效果&#xff0c;已成为众多顶尖汽车制造商的首选方案。然而&#xff0c;当前自动驾驶方案中的大模型算法参数规模剧增&#xff0c;对算力、数据IO及…

【电源专题】BUCK电源SW电压的平均值为什么等于输出电压?

在Buck电源测试过程中,我们会去测试SW开关节点的波形。那么从SW波形中我们能看出什么呢? 首先查看SW波形一般会看SW频率,通过SW波形的频率知道目前芯片的运行状态是什么。比如PSM还是PWM模式。 此外,还会看SW波形的占空比,通过占空比我们可以知道目前输出的状态是怎么样的…

微信分账系统供应链分润微信支付 (亲测源码)

搭建环境&#xff1a;nginxphp7.2mysql5.7 1.上传源码到网站根目录并解压 2.导入数据库文件到数据库 3.修改数据库链接文件/.env 4.设置运行目录为/public 5.伪静态设置成tp 6.后台地址&#xff1a;域名/zh9025.php 源码下载&#xff1a;https://download.csdn.net/down…

HTB:Buff[WriteUP]

目录 连接至HTB服务器并启动靶机 信息搜集 使用rustscan对靶机TCP端口进行开放扫描 使用nmap对靶机开放的端口进行脚本、服务扫描 使用curl分别访问靶机的两个端口 使用浏览器访问靶机8080端口页面 漏洞利用 使用searchsploit搜索该WebAPP 通过python2利用该EXP成功ge…

[UE5学习] 一、使用源代码安装UE5.4

一、简介 本文介绍了如何使用源代码安装编译UE5.4&#xff0c;并且新建简单的项目&#xff0c;打包成安卓平台下的apk安装包。 二、使用源代码安装UE5.4 注意事项&#xff1a; 请保证可以全程流畅地科学上网。请保证C盘具有充足的空间。请保证接下来安装下载的visual studi…

遗传算法(Genetic Algorithm, GA)

简介 遗传算法&#xff08;Genetic Algorithm, GA&#xff09;是一种基于自然选择和遗传机制的优化算法&#xff0c;由 John Holland 于20世纪70年代提出。它是一种模拟生物进化过程的启发式搜索算法&#xff0c;被广泛应用于函数优化、机器学习、调度问题等领域。 代码说明 …

【深度学习之回归预测篇】 深度极限学习机DELM多特征回归拟合预测(Matlab源代码)

深度极限学习机 (DELM) 作为一种新型的深度学习算法&#xff0c;凭借其独特的结构和训练方式&#xff0c;在诸多领域展现出优异的性能。本文将重点探讨DELM在多输入单输出 (MISO) 场景下的应用&#xff0c;深入分析其算法原理、性能特点以及未来发展前景。 1、 DELM算法原理及其…

[Redis#0] iredis: linux上redis超好用的环境配置

目录 Features 特征 Install 安装 Pip Brew Linux的 Download Binary 下载 Binary Usage 用法 Using DSN 使用 DSN Change The Default Prompt更改默认提示 Configuration 配置 Keys Development 发展 Release Strategy 发布策略 Setup Environment 设置环境 De…

软件测试——性能测试概念篇

前言&#xff1a;在完成对web网页或者接口的功能测试后&#xff0c;我们还需要考虑性能方面的因素&#xff0c;在学习完性能测试后&#xff0c;目标是能够对个人编写的项目进行性能测试&#xff0c;找到性能不足的地方&#xff08;性能问题个人很难去解决&#xff0c;如&#x…