搜索与图论——Prim算法求最小生成树
在最小生成树问题里,正边和负边都没问题
朴素版prim算法 时间复杂度O(n^2)
生成树:每一次选中的t点,它和集合的距离对应的那条边,就是生成树的一条边
算法流程和dijkstra算法非常相似
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 510,INF = 0x3f3f3f3f;int n,m;
int g[N][N];
int dist[N];
bool vis[N];int prim(){memset(dist,0x3f,sizeof dist);dist[1] = 0;int res = 0;for(int i = 1; i <= n; i ++ ){int t = -1;for(int j = 1; j <= n; j ++ ){if(!vis[j] && (t == -1 || dist[j] < dist[t])){t = j;}}vis[t] = true;if(dist[t] == INF) return 0;//res的更新要先于dist[t]的更新,因为如果出现负环,就可能导致dist[t]被错误更新,从而导致res的错误res += dist[t];for(int j = 1; j <= n; j ++ ){/* 与dijkstradist[j] = min(dist[j],dist[t] + g[t][j]);不同的是,prim是与g[t][j]作比较,因为dijkstra的dist[j]表示的是j与原点的最短距离,而prim算法中dist[j]表示的是j点与集合的最短距离 */dist[j] = min(dist[j],g[t][j]);}vis[t] = true;}return res;
}int main(){cin >> n >> m;memset(g, 0x3f, sizeof g);while(m -- ){int u,v,w;cin >> u >> v >> w;//无向图是特殊的有向图,建边时只要建一条从a到b的,再建一条从b到a的就可以了g[u][v] = g[v][u] = min(g[u][v],w);}int t = prim();if(!t) cout << "impossible" << endl;else cout << t << endl;return 0;
}
堆优化版prim几乎不会用到,一般直接用kruskal就可以解决。堆优化的prim对比kruskal没有明显优势,还比较难写,故此处不贴模板。
相关文章:

搜索与图论——Prim算法求最小生成树
在最小生成树问题里,正边和负边都没问题 朴素版prim算法 时间复杂度O(n^2) 生成树:每一次选中的t点,它和集合的距离对应的那条边,就是生成树的一条边 算法流程和dijkstra算法非常相似 #include<iostream> #include<cs…...
sqlmap基础知识
一、sqlmap简介 sqlmap是一个开源的渗透测试工具,可以自动检测和利用SQL注入漏洞以及接管数据库服务器的过程。 官网: sqlmap.org 核心功能 漏洞检测漏洞利用 学习关键点 基于sqlmap进行sql注入漏洞的检测,注入利用和攻击基于sqlmap进…...
读《C Primer Plus》
1、汇编语言是为特殊的中央处理单元设计的一系列内部指令,使用助记符来表示;不同的CPU系列使用不同的汇编语言。 2、C语言充分利用计算机优势,使它具有汇编语言才有的微调控能力,可移植性极好。 3、C语言可以访问硬件、操作内存…...

深入理解计算机系统 家庭作业 2.66
/* 前置条件:无符号整数右移不产生1 调用函数是为了可以查看整个过程,不影响结果. 思路是让x在右移的过程中,把最高位之前的位全部填满. 填满后的结果右移一位(即x的最高位变为0,其他为1),再异或x得到最高位 以此类推知道覆盖到32位. */ #include <stdio.h> #inclu…...

【服务端】node.js详细的配置
👨💻个人主页:开发者-曼亿点 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 曼亿点 原创 👨💻 收录于专栏:…...
二、CentOS基础配置(1.网络与包管理)
文章目录 二、基础配置操作1、网络管理(配置静态地址并进行ssh远程连接)(1.)静态地址配置(2.)IP配置注释(3.)配置SSH远程连接 2、包管理(1.)yum软件包管理器1…...
Golang基础-5
Go语言基础 介绍 基础 切片 切片声明 切片初始化 切片基础操作 多维切片 介绍 本文介绍Go语言中切片(slice)(切片声明、切片初始化、切片基础操作、多维切片)等相关知识。 基础 切片 切片(slice)是对数组的一个连续片段的引用,切…...

Mysql数据库:故障分析与配置优化
目录 前言 一、Mysql逻辑架构图 二、Mysql单实例常见故障 1、无法通过套接字连接到本地MySQL服务器 2、用户rootlocalhost访问被拒绝 3、远程连接数据库时连接很慢 4、无法打开以MYI结尾的索引文件 5、超出最大连接错误数量限制 6、连接过多 7、配置文件/etc/my.cnf权…...

常见的图像分析算法
图像分析算法是计算机视觉领域中的一个重要分支,它通过使用预先训练的人工智能模型从图像中提取和分析视觉信息。这些算法可以应用于多种场景,如物体识别、图像分类、图像增强、缺陷检测等。北京木奇移动技术有限公司,专业的软件外包开发公司…...

朵米3.5客服系统源码,附带系统搭建教程
朵米客服系统是一款全功能的客户服务解决方案,提供多渠道支持(如在线聊天、邮件、电话等),帮助企业建立与客户的实时互动。该系统具有智能分流功能,可以快速将客户请求分配给适当的客服人员,提高工作效率。…...
Python 踩坑记
前言 回归 Python 栈,相较 Go 的 Coding,Python 确实偏向复杂,看似编码方便快捷的背后,是越来越庞杂的细枝末节,稍不注意就是偏差。如果项目只是“能跑就行”,那大概率遍地是坑。开启踩坑记~ …...

搭建Spark单机版环境
在搭建Spark单机版环境的实战中,首先确保已经安装并配置好了JDK。然后,从群共享下载Spark安装包,并将其上传至目标主机的/opt目录。接着,解压Spark安装包至/usr/local目录,并配置Spark的环境变量,以确保系统…...

使用Flutter混淆技术保护应用隐私与数据安全
在移动应用开发中,保护应用代码安全至关重要。Flutter 提供了简单易用的混淆工具,帮助开发者在构建 release 版本应用时有效保护代码。本文将介绍如何在 Flutter 应用中使用混淆,并提供了相关的操作步骤和注意事项。 📝 摘要 本…...

ClickHouse初体验
1.clickHouse是啥? ClickHouse 是俄罗斯的 Yandex 于 2016 年开源的列式存储数据库(DBMS),使用 C语言编写,主要用于在线分析处理查询(OLAP),能够使用SQL查询实时生成分析数据报告 2.clickHouse的特点 2.1列式存储 对于列的聚合&…...
在k8s中部署高可用程序实践和资源治理
在k8s中部署高可用程序实践 1. 多副本部署1.1. 副本数量1.2. 更新策略1.3. 跨节点的统一副本分布1.4. 优先级1.5. 停止容器中的进程1.6. 预留资源 2. 探针2.1. 活性探针(liveness probes)2.2. 就绪探针(Readiness probe)2.3. 启动…...
WebView的使用与后退键处理-嵌入小程序或者 H5 页面
在使用 WebView 嵌入小程序或者 H5 页面时,通常会涉及到处理后退键的操作。在 Android 平台上,可以通过 WebView 的相关方法来实现后退键的处理。你可以按照以下步骤来实现: 在 Activity 或 Fragment 中找到 WebView 控件,并为其…...

【攻防世界】file_include (PHP伪协议+过滤器)
打开题目环境: 进行PHP代码审计,发现这是一个文件包含漏洞。 我们尝试利用PHP伪协议中的 php://filter来读取 check.php 中的内容。 构造payload 并提交: 发现payload被过滤掉了,我们就需要尝试使用不同的转换器。 PHP各类转换…...
Linux 内核中PHY子系统(网络):PHY驱动
一. 简介 PHY 子系统就是用于 PHY 设备相关内容的,分为 PHY 设备和 PHY 驱动,和 platform 总线一样,PHY 子系统也是一个设备、总线和驱动模型。 前面一篇文章学习了 PHY子系统中的 PHY设备。文章如下: Linux 内核中PHY子系统(网…...
【六 (1)机器学习-机器学习算法简介】
目录 文章导航一、机器学习二、基于学习方式的分类三、监督学习常见类型四、无监督学习常见类型五、强化学习常见分类 文章导航 【一 简明数据分析进阶路径介绍(文章导航)】 一、机器学习 机器学习是一门多领域交叉学科,涉及概率论、统计学…...
TCP服务端主动向客户端发送数据
C TCP 服务端和客户端通信的例子 在此基础上,要修改服务端代码,使其能够每秒向客户端发送当前时间,你需要添加一个循环,每次循环发送当前时间给客户端。同时,你需要在客户端代码中添加接收服务端发送的数据的逻辑。 …...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...

企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...
Linux安全加固:从攻防视角构建系统免疫
Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

对象回调初步研究
_OBJECT_TYPE结构分析 在介绍什么是对象回调前,首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例,用_OBJECT_TYPE这个结构来解析它,0x80处就是今天要介绍的回调链表,但是先不着急,先把目光…...