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

堆优化版本的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每轮找最小边的松弛操作其实是同源的&#xff0c;因而受dijkstra堆优化的启发&#xff0c;那么prim也可以采用小根堆进行优化。时间复杂度也由 O ( n 2 ) O(n^2) O(n2)降为 O ( n l o g n ) O(nlogn) O(nlogn)。 测试一下吧&#xff1a;原题链接 #include <i…...

Ubuntu上安装MySQL并且实现远程登录

目录 下载网络工具 查看网络连接 更新系统软件包&#xff1b; 安装mysql数据库 查看mysql数据库状态 以数字ip形式显示mysql的监听状态。&#xff08;默认监听端口是3306&#xff09; 查看安装mysql数据库时系统创建的目录信息。 根据查询到的系统用户名以及随机密码&a…...

蓝桥杯每日真题 - 第21天

题目&#xff1a;(空间) 题目描述&#xff08;12届 C&C B组A题&#xff09; 解题思路&#xff1a; 转换单位&#xff1a; 内存总大小为 256MB&#xff0c;换算为字节&#xff1a; 25610241024268,435,456字节 计算每个整数占用空间&#xff1a; 每个 32 位整数占用…...

(长期更新)《零基础入门 ArcGIS(ArcMap) 》实验一(下)----空间数据的编辑与处理(超超超详细!!!)

续上篇博客&#xff08;长期更新&#xff09;《零基础入门 ArcGIS(ArcMap) 》实验一&#xff08;上&#xff09;----空间数据的编辑与处理&#xff08;超超超详细&#xff01;&#xff01;&#xff01;&#xff09;-CSDN博客 继续更新 目录 什么是拓扑&#xff1f; 1.3.5道路…...

NLP论文速读(CVPR 2024)|使用DPO进行diffusion模型对齐

论文速读|Diffusion Model Alignment Using Direct Preference Optimization 论文信息&#xff1a; 简介&#xff1a; 本文探讨的背景是大型语言模型&#xff08;LLMs&#xff09;通过人类比较数据和从人类反馈中学习&#xff08;RLHF&#xff09;的方法进行微调&#xff0c;以…...

操作系统——揭开盖子

计算机执行时——取指执行 es:bx等于从0x9000开始&#xff0c;到0x90200结束...

如何在 React 项目中应用 TypeScript?应该注意那些点?结合实际项目示例及代码进行讲解!

在 React 项目中应用 TypeScript 是提升开发效率、增强代码可维护性和可读性的好方法。TypeScript 提供了静态类型检查、自动补全和代码提示等功能&#xff0c;这对于 React 开发者来说&#xff0c;能够帮助早期发现潜在的 bug&#xff0c;提高开发体验。 1. 项目初始化 在现…...

C++学习第四天

创作过程中难免有不足&#xff0c;若您发现本文内容有误&#xff0c;恳请不吝赐教。 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、计算类对象的大小 #include<iostream> using namespace std;class Date { public:void Init(int year, in…...

【从零开始的LeetCode-算法】3232. 判断是否可以赢得数字游戏

给你一个 正整数 数组 nums。 Alice 和 Bob 正在玩游戏。在游戏中&#xff0c;Alice 可以从 nums 中选择所有个位数 或 所有两位数&#xff0c;剩余的数字归 Bob 所有。如果 Alice 所选数字之和 严格大于 Bob 的数字之和&#xff0c;则 Alice 获胜。 如果 Alice 能赢得这场游…...

一种简单高效的RTSP流在线检测方法,不需要再过渡拉流就可以获取设备状态以及对应音视频通道与编码格式

平台如何检测一路RTSP流是否在线&#xff1f; 在之前的流媒体平台方案中&#xff0c;我们都是通过定时RTSP拉流的方式&#xff0c;走一个完整的RTSP流程&#xff1a;包括OPTIONS、DESCRIBE、SETUP、PLAY、RTP收流&#xff0c;这种方式去取流&#xff0c;然后取到流之后进行流解…...

24/11/22 项目拆解 艺术风格转移

我们有时候想把两种艺术风格整合&#xff0c;创造更具艺术特色的艺术品&#xff0c;人很难办到&#xff0c;但是人工智能可以,比如下面将艺术画的风格转移到照片上。 我们先来初步了解一下实现上述功能的数学原理 所谓艺术风格&#xff0c;其实就是边缘&#xff0c;颜色&#…...

数字赋能,气象引领 | 气象景观数字化服务平台重塑京城旅游生态

在数字化转型的浪潮中&#xff0c;旅游行业正以前所未有的速度重塑自身&#xff0c;人民群众对于高品质、个性化旅游服务需求的日益增长&#xff0c;迎着新时代的挑战与机遇&#xff0c;为开展北京地区特色气象景观预报&#xff0c;打造“生态气象旅游”新业态&#xff0c;助推…...

关于Redux的学习(包括Redux-toolkit中间件)

目录 什么是 Redux &#xff1f; 我为什么要用 Redux &#xff1f; 我什么时候应该用 Redux &#xff1f; Redux 库和工具 React-Redux Redux Toolkit Redux DevTools 拓展 一个redux小示例 代码示例(很有用)&#xff1a; Redux 术语 Actions Reducers Store Dis…...

【无人机】

GJI Mini 4 Pro学习 首次飞行使用 01 开箱 打开长飞套装 依次取出产品及配件 飞行器、DJI RC - N2&#xff08;DJI RC 2&#xff09;、桨叶/螺丝、云台保护罩、束桨器、电池、螺丝刀、USB-C快接线、单肩包、USB-C数据线、充电管家 02 准备飞行器 取下束桨器&#xff0c;…...

Zabbix7.0.6的容器镜像准备

准备Zabbix7.0.6部署所需的容器镜像。 更新时间&#xff1a;20241122 一、准备数据库镜像 1、核对版本支持 根据Zabbix官网文档requirements 可知&#xff0c;当前最新的Zabbix 7.0.6对PostgreSQL数据库的要求如下&#xff1a; support for PostgreSQL versions:- 17.X …...

利用 GitHub 和 Hexo 搭建个人博客【保姆教程】

利用 GitHub 和 Hexo 搭建个人博客 利用 GitHub 和 Hexo 搭建个人博客一、前言二、准备工作&#xff08;一&#xff09;安装 Node.js 和 Git&#xff08;二&#xff09;注册 GitHub 账号 三、安装 Hexo&#xff08;一&#xff09;创建博客目录&#xff08;二&#xff09;安装 H…...

React第四节 组件的三大属性之state

前言 状态 state适用于类式组件中&#xff0c;而再函数式组件中需要使用 useState HOOK 模拟状态; React的组件就是一个状态机&#xff0c;通过与用户的交互&#xff0c;实现不同的状态&#xff0c;根据不同的状态展现出不一样的UI视图 并不是组件中所有的属性 都是组件的状态…...

MongoDB进阶篇-索引(索引概述、索引的类型、索引相关操作、索引的使用)

文章目录 1. 索引概述2. 索引的类型2.1 单字段索引2.2 复合索引2.3 其他索引2.3.1 地理空间索引&#xff08;Geospatial Index&#xff09;2.3.2 文本索引&#xff08;Text Indexes&#xff09;2.3.3 哈希索引&#xff08;Hashed Indexes&#xff09; 3. 索引相关操作3.1 查看索…...

使用FFmpeg实现视频与GIF的画中画效果

用FFmpeg命令行工具将GIF动画作为画中画&#xff08;Picture-in-Picture&#xff0c;简称PiP&#xff09;叠加到视频上。FFmpeg是一个强大的多媒体框架&#xff0c;能够处理几乎所有格式的音频和视频文件。通过这个教程&#xff0c;你将学会如何将一个小的GIF动画循环播放&…...

车载信息安全框架 --- 车载信息安全相关事宜

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所有人的看法和评价都是暂时的,只有自己的经历是伴随一生的,几乎所有的担忧和畏惧,都是来源于自己的想象,只有你真的去做了,才会发现有多快乐。…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

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.…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...