acwing算法基础之搜索与图论--prim算法
目录
- 1 基础知识
- 2 模板
- 3 工程化
1 基础知识
朴素版prim算法的关键步骤:
- 初始化距离数组dist,将其内的所有元素都设为正无穷大。
- 定义集合S,表示生成树。
- 循环n次:找到不在集合S中且距离集合S最近的结点t,用它去更新剩余结点到集合S的距离。
- 最小生成树建立完毕,边长之和等于每次的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算法的关键步骤: 初始化距离数组dist,将其内的所有元素都设为正无穷大。定义集合S,表示生成树。循环n次:找到不在集合S中且距离集合S最近的结点t,用它去更新剩余…...
Amazon EC2 Serial Console 现已在其他亚马逊云科技区域推出
即日起,交互式 EC2 Serial Console 现也在以下区域推出:中东(巴林)、亚太地区(雅加达)、非洲(开普敦)、中东(阿联酋)、亚太地区(香港)…...
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请求: def start_requests(self):self.headers {Content-Type: application/json}json_data {"productName": "", "currentPage": "1", "recordNumber": "10", "langua…...
一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?
目录 1解题思路: 2代码如下: 3运行结果: 4总结: 5介绍: 1解题思路: 利用循环(穷举法)来 对 所 需要的数 进行确定 2代码如下: #include <stdio.h>int main() …...
自主开发刷题应用网站H5源码(无需后端无需数据库)
该应用使用JSON作为题库的存储方式,层次清晰、结构简单易懂。 配套的word模板和模板到JSON转换工具可供使用,方便将题库从word格式转换为JSON格式。 四种刷题模式包括顺序刷题、乱序刷题、错题模式和背题模式,可以根据自己的需求选择适合的模…...
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 是西门子(Siemens)公司生产的一款模块化可编程逻辑控制器(PL…...
消息队列简介
消息队列 在认识rabbitMQ之前,我们需要先认识下消息队列。 消息队列,一般简称为MQ(Message Queue)。先不管消息(Message)这个词,先看看队列(Queue)。 队列就是一种先进先出的数据结构。 所以消息队列可以简单理解为&a…...
SQL中实现汉字的拼音首字母查询
由于汉语拼音首字母也就23个,该方法利用汉字字符按拼音字母排序的特点来生成对应的拼单首字母,只需找到这23个汉语拼音首字母中分别排序在第一的汉字生成23条临时表数据用于参照,即可简单实现汉字匹配拼音首字母 CREATE FUNCTION f_GetPyAcr…...
今天知道LiveData的ktx是真的香
主要还是认知问题,Android 官网从一开始就在推ktx,现在都已经2. 版本了,但是呢,因为之前没有从0开始写过一个Kotlin的APP,就陷入了一个JAVA 思维,在JAVA 中我们知道要做到像协程这么处理不是不能࿰…...
SpringBoot中的桥接模式
桥接模式是一种结构型设计模式,它的主要目的是通过将抽象部分与实现部分分离,提高系统的灵活性和可扩展性。在桥接模式中,有四个主要参与者:抽象类、具体抽象类、桥接类和具体类。 抽象类是定义了抽象方法的基类,这些…...
AI爆文变现脚本:易用且免费的自动写作脚本更新了
之前给大家分享的AI爆文变现写作脚本 由于时间仓促,加上我对很多东西不熟悉 免费版本对新手小白来说,安装部署起来是非常的困难 于是这几天我加班加点把整个软件的部署简化 现在无需复杂的环境配置安装,下载配置下就可以使用了。 免费版…...
代码随想录算法训练营Day 49 || 123.买卖股票的最佳时机III 、188.买卖股票的最佳时机IV
123.买卖股票的最佳时机III 力扣题目链接(opens new window) 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意:你不能同时参与多笔交易(你必须…...
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 问题如图所示: 解决办法: 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 从目标字符串的角度来看,LC139是一个排列问题,因为最终目标子串的各个字符的顺序是固定的? 当我们从目标字符串 s 的角度来看 LC139 “单词拆分” 问题,确实可以认为它涉及到排列的概念,但这种…...
火星加载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&…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
