搜索与图论——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 服务端和客户端通信的例子 在此基础上,要修改服务端代码,使其能够每秒向客户端发送当前时间,你需要添加一个循环,每次循环发送当前时间给客户端。同时,你需要在客户端代码中添加接收服务端发送的数据的逻辑。 …...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...