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

搜索与图论——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算法求最小生成树

在最小生成树问题里&#xff0c;正边和负边都没问题 朴素版prim算法 时间复杂度O(n^2) 生成树&#xff1a;每一次选中的t点&#xff0c;它和集合的距离对应的那条边&#xff0c;就是生成树的一条边 算法流程和dijkstra算法非常相似 #include<iostream> #include<cs…...

sqlmap基础知识

一、sqlmap简介 sqlmap是一个开源的渗透测试工具&#xff0c;可以自动检测和利用SQL注入漏洞以及接管数据库服务器的过程。 官网&#xff1a; sqlmap.org 核心功能 漏洞检测漏洞利用 学习关键点 基于sqlmap进行sql注入漏洞的检测&#xff0c;注入利用和攻击基于sqlmap进…...

读《C Primer Plus》

1、汇编语言是为特殊的中央处理单元设计的一系列内部指令&#xff0c;使用助记符来表示&#xff1b;不同的CPU系列使用不同的汇编语言。 2、C语言充分利用计算机优势&#xff0c;使它具有汇编语言才有的微调控能力&#xff0c;可移植性极好。 3、C语言可以访问硬件、操作内存…...

深入理解计算机系统 家庭作业 2.66

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

【服务端】node.js详细的配置

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…...

二、CentOS基础配置(1.网络与包管理)

文章目录 二、基础配置操作1、网络管理&#xff08;配置静态地址并进行ssh远程连接&#xff09;&#xff08;1.&#xff09;静态地址配置&#xff08;2.&#xff09;IP配置注释&#xff08;3.&#xff09;配置SSH远程连接 2、包管理&#xff08;1.&#xff09;yum软件包管理器1…...

Golang基础-5

Go语言基础 介绍 基础 切片 切片声明 切片初始化 切片基础操作 多维切片 介绍 本文介绍Go语言中切片(slice)(切片声明、切片初始化、切片基础操作、多维切片)等相关知识。 基础 切片 切片&#xff08;slice&#xff09;是对数组的一个连续片段的引用&#xff0c;切…...

Mysql数据库:故障分析与配置优化

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

常见的图像分析算法

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

朵米3.5客服系统源码,附带系统搭建教程

朵米客服系统是一款全功能的客户服务解决方案&#xff0c;提供多渠道支持&#xff08;如在线聊天、邮件、电话等&#xff09;&#xff0c;帮助企业建立与客户的实时互动。该系统具有智能分流功能&#xff0c;可以快速将客户请求分配给适当的客服人员&#xff0c;提高工作效率。…...

Python 踩坑记

前言 回归 Python 栈&#xff0c;相较 Go 的 Coding&#xff0c;Python 确实偏向复杂&#xff0c;看似编码方便快捷的背后&#xff0c;是越来越庞杂的细枝末节&#xff0c;稍不注意就是偏差。如果项目只是“能跑就行”&#xff0c;那大概率遍地是坑。开启踩坑记&#xff5e; …...

搭建Spark单机版环境

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

使用Flutter混淆技术保护应用隐私与数据安全

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

ClickHouse初体验

1.clickHouse是啥&#xff1f; ClickHouse 是俄罗斯的 Yandex 于 2016 年开源的列式存储数据库(DBMS)&#xff0c;使用 C语言编写&#xff0c;主要用于在线分析处理查询(OLAP)&#xff0c;能够使用SQL查询实时生成分析数据报告 2.clickHouse的特点 2.1列式存储 对于列的聚合&…...

在k8s中部署高可用程序实践和资源治理

在k8s中部署高可用程序实践 1. 多副本部署1.1. 副本数量1.2. 更新策略1.3. 跨节点的统一副本分布1.4. 优先级1.5. 停止容器中的进程1.6. 预留资源 2. 探针2.1. 活性探针&#xff08;liveness probes&#xff09;2.2. 就绪探针&#xff08;Readiness probe&#xff09;2.3. 启动…...

WebView的使用与后退键处理-嵌入小程序或者 H5 页面

在使用 WebView 嵌入小程序或者 H5 页面时&#xff0c;通常会涉及到处理后退键的操作。在 Android 平台上&#xff0c;可以通过 WebView 的相关方法来实现后退键的处理。你可以按照以下步骤来实现&#xff1a; 在 Activity 或 Fragment 中找到 WebView 控件&#xff0c;并为其…...

【攻防世界】file_include (PHP伪协议+过滤器)

打开题目环境&#xff1a; 进行PHP代码审计&#xff0c;发现这是一个文件包含漏洞。 我们尝试利用PHP伪协议中的 php://filter来读取 check.php 中的内容。 构造payload 并提交&#xff1a; 发现payload被过滤掉了&#xff0c;我们就需要尝试使用不同的转换器。 PHP各类转换…...

Linux 内核中PHY子系统(网络):PHY驱动

一. 简介 PHY 子系统就是用于 PHY 设备相关内容的&#xff0c;分为 PHY 设备和 PHY 驱动&#xff0c;和 platform 总线一样&#xff0c;PHY 子系统也是一个设备、总线和驱动模型。 前面一篇文章学习了 PHY子系统中的 PHY设备。文章如下&#xff1a; Linux 内核中PHY子系统(网…...

【六 (1)机器学习-机器学习算法简介】

目录 文章导航一、机器学习二、基于学习方式的分类三、监督学习常见类型四、无监督学习常见类型五、强化学习常见分类 文章导航 【一 简明数据分析进阶路径介绍&#xff08;文章导航&#xff09;】 一、机器学习 机器学习是一门多领域交叉学科&#xff0c;涉及概率论、统计学…...

TCP服务端主动向客户端发送数据

C TCP 服务端和客户端通信的例子 在此基础上&#xff0c;要修改服务端代码&#xff0c;使其能够每秒向客户端发送当前时间&#xff0c;你需要添加一个循环&#xff0c;每次循环发送当前时间给客户端。同时&#xff0c;你需要在客户端代码中添加接收服务端发送的数据的逻辑。 …...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...