堆优化版本的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;
}
相关文章:
堆优化版本的Prim
prim和dijkstra每轮找最小边的松弛操作其实是同源的,因而受dijkstra堆优化的启发,那么prim也可以采用小根堆进行优化。时间复杂度也由 O ( n 2 ) O(n^2) O(n2)降为 O ( n l o g n ) O(nlogn) O(nlogn)。 测试一下吧:原题链接 #include <i…...
Ubuntu上安装MySQL并且实现远程登录
目录 下载网络工具 查看网络连接 更新系统软件包; 安装mysql数据库 查看mysql数据库状态 以数字ip形式显示mysql的监听状态。(默认监听端口是3306) 查看安装mysql数据库时系统创建的目录信息。 根据查询到的系统用户名以及随机密码&a…...
蓝桥杯每日真题 - 第21天
题目:(空间) 题目描述(12届 C&C B组A题) 解题思路: 转换单位: 内存总大小为 256MB,换算为字节: 25610241024268,435,456字节 计算每个整数占用空间: 每个 32 位整数占用…...
(长期更新)《零基础入门 ArcGIS(ArcMap) 》实验一(下)----空间数据的编辑与处理(超超超详细!!!)
续上篇博客(长期更新)《零基础入门 ArcGIS(ArcMap) 》实验一(上)----空间数据的编辑与处理(超超超详细!!!)-CSDN博客 继续更新 目录 什么是拓扑? 1.3.5道路…...
NLP论文速读(CVPR 2024)|使用DPO进行diffusion模型对齐
论文速读|Diffusion Model Alignment Using Direct Preference Optimization 论文信息: 简介: 本文探讨的背景是大型语言模型(LLMs)通过人类比较数据和从人类反馈中学习(RLHF)的方法进行微调,以…...
操作系统——揭开盖子
计算机执行时——取指执行 es:bx等于从0x9000开始,到0x90200结束...
如何在 React 项目中应用 TypeScript?应该注意那些点?结合实际项目示例及代码进行讲解!
在 React 项目中应用 TypeScript 是提升开发效率、增强代码可维护性和可读性的好方法。TypeScript 提供了静态类型检查、自动补全和代码提示等功能,这对于 React 开发者来说,能够帮助早期发现潜在的 bug,提高开发体验。 1. 项目初始化 在现…...
C++学习第四天
创作过程中难免有不足,若您发现本文内容有误,恳请不吝赐教。 提示:以下是本篇文章正文内容,下面案例可供参考 一、计算类对象的大小 #include<iostream> using namespace std;class Date { public:void Init(int year, in…...
【从零开始的LeetCode-算法】3232. 判断是否可以赢得数字游戏
给你一个 正整数 数组 nums。 Alice 和 Bob 正在玩游戏。在游戏中,Alice 可以从 nums 中选择所有个位数 或 所有两位数,剩余的数字归 Bob 所有。如果 Alice 所选数字之和 严格大于 Bob 的数字之和,则 Alice 获胜。 如果 Alice 能赢得这场游…...
一种简单高效的RTSP流在线检测方法,不需要再过渡拉流就可以获取设备状态以及对应音视频通道与编码格式
平台如何检测一路RTSP流是否在线? 在之前的流媒体平台方案中,我们都是通过定时RTSP拉流的方式,走一个完整的RTSP流程:包括OPTIONS、DESCRIBE、SETUP、PLAY、RTP收流,这种方式去取流,然后取到流之后进行流解…...
24/11/22 项目拆解 艺术风格转移
我们有时候想把两种艺术风格整合,创造更具艺术特色的艺术品,人很难办到,但是人工智能可以,比如下面将艺术画的风格转移到照片上。 我们先来初步了解一下实现上述功能的数学原理 所谓艺术风格,其实就是边缘,颜色&#…...
数字赋能,气象引领 | 气象景观数字化服务平台重塑京城旅游生态
在数字化转型的浪潮中,旅游行业正以前所未有的速度重塑自身,人民群众对于高品质、个性化旅游服务需求的日益增长,迎着新时代的挑战与机遇,为开展北京地区特色气象景观预报,打造“生态气象旅游”新业态,助推…...
关于Redux的学习(包括Redux-toolkit中间件)
目录 什么是 Redux ? 我为什么要用 Redux ? 我什么时候应该用 Redux ? Redux 库和工具 React-Redux Redux Toolkit Redux DevTools 拓展 一个redux小示例 代码示例(很有用): Redux 术语 Actions Reducers Store Dis…...
【无人机】
GJI Mini 4 Pro学习 首次飞行使用 01 开箱 打开长飞套装 依次取出产品及配件 飞行器、DJI RC - N2(DJI RC 2)、桨叶/螺丝、云台保护罩、束桨器、电池、螺丝刀、USB-C快接线、单肩包、USB-C数据线、充电管家 02 准备飞行器 取下束桨器,…...
Zabbix7.0.6的容器镜像准备
准备Zabbix7.0.6部署所需的容器镜像。 更新时间:20241122 一、准备数据库镜像 1、核对版本支持 根据Zabbix官网文档requirements 可知,当前最新的Zabbix 7.0.6对PostgreSQL数据库的要求如下: support for PostgreSQL versions:- 17.X …...
利用 GitHub 和 Hexo 搭建个人博客【保姆教程】
利用 GitHub 和 Hexo 搭建个人博客 利用 GitHub 和 Hexo 搭建个人博客一、前言二、准备工作(一)安装 Node.js 和 Git(二)注册 GitHub 账号 三、安装 Hexo(一)创建博客目录(二)安装 H…...
React第四节 组件的三大属性之state
前言 状态 state适用于类式组件中,而再函数式组件中需要使用 useState HOOK 模拟状态; React的组件就是一个状态机,通过与用户的交互,实现不同的状态,根据不同的状态展现出不一样的UI视图 并不是组件中所有的属性 都是组件的状态…...
MongoDB进阶篇-索引(索引概述、索引的类型、索引相关操作、索引的使用)
文章目录 1. 索引概述2. 索引的类型2.1 单字段索引2.2 复合索引2.3 其他索引2.3.1 地理空间索引(Geospatial Index)2.3.2 文本索引(Text Indexes)2.3.3 哈希索引(Hashed Indexes) 3. 索引相关操作3.1 查看索…...
使用FFmpeg实现视频与GIF的画中画效果
用FFmpeg命令行工具将GIF动画作为画中画(Picture-in-Picture,简称PiP)叠加到视频上。FFmpeg是一个强大的多媒体框架,能够处理几乎所有格式的音频和视频文件。通过这个教程,你将学会如何将一个小的GIF动画循环播放&…...
车载信息安全框架 --- 车载信息安全相关事宜
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所有人的看法和评价都是暂时的,只有自己的经历是伴随一生的,几乎所有的担忧和畏惧,都是来源于自己的想象,只有你真的去做了,才会发现有多快乐。…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
鸿蒙HarmonyOS 5军旗小游戏实现指南
1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发,采用DevEco Studio实现,包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...
JS红宝书笔记 - 3.3 变量
要定义变量,可以使用var操作符,后跟变量名 ES实现变量初始化,因此可以同时定义变量并设置它的值 使用var操作符定义的变量会成为包含它的函数的局部变量。 在函数内定义变量时省略var操作符,可以创建一个全局变量 如果需要定义…...
