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

acwing算法基础之搜索与图论--prim算法

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

朴素版prim算法的关键步骤:

  1. 初始化距离数组dist,将其内的所有元素都设为正无穷大。
  2. 定义集合S,表示生成树。
  3. 循环n次:找到不在集合S中且距离集合S最近的结点t,用它去更新剩余结点到集合S的距离。
  4. 最小生成树建立完毕,边长之和等于每次的d[t]之和。

朴素版prim算法的时间复杂度为O(n^2),它用来解决稠密图的最小生成树问题。

2 模板

int n;      // n表示点数
int g[N][N];        // 邻接矩阵,存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{memset(dist, 0x3f, sizeof dist);int res = 0;for (int i = 0; i < n; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;if (i && dist[t] == INF) return INF;if (i) res += dist[t];st[t] = true;for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);}return res;
}

3 工程化

题目1:求最小生成树。

#include <iostream>
#include <cstring>using namespace std;const int N = 510;
int g[N][N];
int d[N];
bool st[N];
int n, m;void prim() {memset(d, 0x3f, sizeof d);int res = 0;for (int i = 0; i < n; ++i) {//n次循环//找到不在集合S且距离集合S最小的结点int t = -1;for (int j = 1; j <= n; ++j) {if (!st[j] && (t == -1 || d[t] > d[j])) {t = j;}}if (i && d[t] == 0x3f3f3f3f) {cout << "impossible" << endl;return;}st[t] = true;if (i) res += d[t];//用t去更新其它结点for (int j = 1; j <= n; ++j) {if (d[j] > g[t][j]) {d[j] = g[t][j];}}}cout << res << endl;return;
}int main() {cin >> n >> m;memset(g, 0x3f, sizeof g);int a, b, c;while (m--) {cin >> a >> b >> c;g[a][b] = min(g[a][b], c);g[b][a] = min(g[b][a], c);}prim();return 0;
}

相关文章:

acwing算法基础之搜索与图论--prim算法

目录 1 基础知识2 模板3 工程化 1 基础知识 朴素版prim算法的关键步骤&#xff1a; 初始化距离数组dist&#xff0c;将其内的所有元素都设为正无穷大。定义集合S&#xff0c;表示生成树。循环n次&#xff1a;找到不在集合S中且距离集合S最近的结点t&#xff0c;用它去更新剩余…...

Amazon EC2 Serial Console 现已在其他亚马逊云科技区域推出

即日起&#xff0c;交互式 EC2 Serial Console 现也在以下区域推出&#xff1a;中东&#xff08;巴林&#xff09;、亚太地区&#xff08;雅加达&#xff09;、非洲&#xff08;开普敦&#xff09;、中东&#xff08;阿联酋&#xff09;、亚太地区&#xff08;香港&#xff09;…...

hdlbits系列verilog解答(100输入逻辑门)-39

文章目录 一、问题描述二、verilog源码三、仿真结果一、问题描述 构建一个具有 100 个输入in[99:0]的组合电路。 有 3 个输出: out_and: output of a 100-input AND gate. out_or: output of a 100-input OR gate. out_xor: output of a 100-input XOR gate. 二、verilog源…...

Python 中 Selenium 的屏幕截图

文章目录 使用 save_screenshot() 函数在 Python 中使用 selenium 捕获屏幕截图使用 get_screenshot_as_file() 函数在 Python 中使用 selenium 捕获屏幕截图使用 Screenshot-Selenium 包在 Python 中使用 selenium 捕获屏幕截图总结我们可以使用 Selenium 在自动化 Web 浏览器…...

scrapy发json的post请求

一 、scrapy发json的post请求&#xff1a; def start_requests(self):self.headers {Content-Type: application/json}json_data {"productName": "", "currentPage": "1", "recordNumber": "10", "langua…...

一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?

目录 1解题思路&#xff1a; 2代码如下&#xff1a; 3运行结果&#xff1a; 4总结&#xff1a; 5介绍&#xff1a; 1解题思路&#xff1a; 利用循环&#xff08;穷举法&#xff09;来 对 所 需要的数 进行确定 2代码如下&#xff1a; #include <stdio.h>int main() …...

自主开发刷题应用网站H5源码(无需后端无需数据库)

该应用使用JSON作为题库的存储方式&#xff0c;层次清晰、结构简单易懂。 配套的word模板和模板到JSON转换工具可供使用&#xff0c;方便将题库从word格式转换为JSON格式。 四种刷题模式包括顺序刷题、乱序刷题、错题模式和背题模式&#xff0c;可以根据自己的需求选择适合的模…...

java 读取excel/word存入mysql

引入依赖 <!--poi--><dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>4.0.1</version></dependency><dependency><groupId>org.apache.poi</groupId><artif…...

11.(vue3.x+vite)组件间通信方式之ref与$parent、$children

前端技术社区总目录(订阅之前请先查看该博客) 示例效果 注: (1)ref 加在标签(div等)上,是拿到dom 对象 (2)ref加上组件上,拿到的是组件的引用 (3)让父组件获取子组件的数据或者方法需要通过defineExpose对外暴露,另外让父组件获取子组件的数据或者方法需要通过d…...

[工业自动化-12]:西门子S7-15xxx编程 - PLC从站 - ET200 SP系列详解

目录 一、概述 1.1 概述 二、系统组成 2.1 概述 2.2 与主站的通信接口模块 2.3 总线适配器 2.4 基座单元 2.5 电子模块 2.6 服务器模块 一、概述 1.1 概述 PLC ET200 SP 是西门子&#xff08;Siemens&#xff09;公司生产的一款模块化可编程逻辑控制器&#xff08;PL…...

消息队列简介

消息队列 在认识rabbitMQ之前&#xff0c;我们需要先认识下消息队列。 消息队列&#xff0c;一般简称为MQ&#xff08;Message Queue&#xff09;。先不管消息(Message)这个词&#xff0c;先看看队列(Queue)。 队列就是一种先进先出的数据结构。 所以消息队列可以简单理解为&a…...

SQL中实现汉字的拼音首字母查询

由于汉语拼音首字母也就23个&#xff0c;该方法利用汉字字符按拼音字母排序的特点来生成对应的拼单首字母&#xff0c;只需找到这23个汉语拼音首字母中分别排序在第一的汉字生成23条临时表数据用于参照&#xff0c;即可简单实现汉字匹配拼音首字母 CREATE FUNCTION f_GetPyAcr…...

今天知道LiveData的ktx是真的香

主要还是认知问题&#xff0c;Android 官网从一开始就在推ktx&#xff0c;现在都已经2. 版本了&#xff0c;但是呢&#xff0c;因为之前没有从0开始写过一个Kotlin的APP&#xff0c;就陷入了一个JAVA 思维&#xff0c;在JAVA 中我们知道要做到像协程这么处理不是不能&#xff0…...

SpringBoot中的桥接模式

桥接模式是一种结构型设计模式&#xff0c;它的主要目的是通过将抽象部分与实现部分分离&#xff0c;提高系统的灵活性和可扩展性。在桥接模式中&#xff0c;有四个主要参与者&#xff1a;抽象类、具体抽象类、桥接类和具体类。 抽象类是定义了抽象方法的基类&#xff0c;这些…...

AI爆文变现脚本:易用且免费的自动写作脚本更新了

之前给大家分享的AI爆文变现写作脚本 由于时间仓促&#xff0c;加上我对很多东西不熟悉 免费版本对新手小白来说&#xff0c;安装部署起来是非常的困难 于是这几天我加班加点把整个软件的部署简化 现在无需复杂的环境配置安装&#xff0c;下载配置下就可以使用了。 免费版…...

代码随想录算法训练营Day 49 || 123.买卖股票的最佳时机III 、188.买卖股票的最佳时机IV

123.买卖股票的最佳时机III 力扣题目链接(opens new window) 给定一个数组&#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意&#xff1a;你不能同时参与多笔交易&#xff08;你必须…...

threejs(11)-精通着色器编程(难点)2

一、shader着色器编写高级图案 小日本国旗 precision lowp float; varying vec2 vUv; float strength step(0.5,distance(vUv,vec2(0.5))0.25) ; gl_FragColor vec4(strength,strength,strength,strength);绘制圆 precision lowp float; varying vec2 vUv; float strength 1…...

配置cuda和cudnn出现 libcudnn.so.8 is not a symbolic link问题

cuda版本为11.2 问题如图所示&#xff1a; 解决办法&#xff1a; sudo ln -sf /usr/local/cuda-11.2/targets/x86_64-linux/lib/libcudnn_adv_train.so.8.1.1 /usr/local/cuda-11.2/targets/x86_64-linux/lib/libcudnn_adv_train.so.8 sudo ln -sf /usr/local/cuda-11.2/targ…...

“目标值排列匹配“和“背包组合问题“的区别和leetcode例题详解

1 目标值排列匹配 1.1 从目标字符串的角度来看&#xff0c;LC139是一个排列问题&#xff0c;因为最终目标子串的各个字符的顺序是固定的&#xff1f; 当我们从目标字符串 s 的角度来看 LC139 “单词拆分” 问题&#xff0c;确实可以认为它涉及到排列的概念&#xff0c;但这种…...

火星加载WMTS服务

这是正常的加载瓦片 http://192.168.1.23:8008/geoserver/mars3d/gwc/service/wmts?tilematrixEPSG%3A4326%3A7&layermars3d%3Abuffer&style&tilerow46&tilecol197&tilematrixsetEPSG%3A4326&formatimage%2Fpng&serviceWMTS&version1.0.0&…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...