当前位置: 首页 > 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;你需要在客户端代码中添加接收服务端发送的数据的逻辑。 …...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...