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

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

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

文章目录 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…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...