P3366 【模板】最小生成树-Prim

2024-08-23 15:58
文章标签 模板 最小 生成 prim p3366

本文主要是介绍P3366 【模板】最小生成树-Prim,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法原理:

  • 在kruskal算法正确性的基础上,考虑进行优化.
  • 由于kruskal的复杂度为O(mlogm),在稠密图中表现可能不太好,思考能否利用最短这一性质对复杂度上界进行优化.
  • 联想到dijkstra的性质,可以发现最小生成树在局部也满足这一性质(最小生成树的每一个子树都是一个最小生成树).
  • 由于任意一点都必然会在最小生成树中,可以从任意一点开始"探索"(类似文明VI中探索地图).
  • 假设首先选择了1号点,那么对于1号点来说,如果想要拓展自己的大小且花费尽量小,应该选择权值最小的边.
  • 递归进行以上操作,就可以求出整个图的最小生成树.

堆优化:

  • 考虑到在最小生成树的拓展过程中,每个点在被选择时,它所在的"入边"一定是最优选择,而已有的最小生成树可以证明是完美的,而且每个点实际上仅仅是对于其他点的一个"中转站",所以它的"入边"就不需要再被更新。可以利用这一个性质,结合Dijkstra的堆优化,将"入边"长度作为小根堆的特征值,即可将算法复杂度从O(n^2)优化到O(nlogm)

题目地址


#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=5e3+5,MAXM=4e5+5;
struct Edge{int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,int w){e[++edgeCnt].from=u;e[edgeCnt].to=v;e[edgeCnt].w=w;e[edgeCnt].nxt=head[u];head[u]=edgeCnt;
}
struct Node{int nowV,nowW;bool operator <(Node another)const{return nowW>another.nowW;}
};
int minw[MAXM];
bool vis[MAXN];
int prim(){memset(minw,0x3f,sizeof(minw));priority_queue<Node> q;q.push(Node{1,0});int ans=0;while(!q.empty()){Node nowNode=q.top();q.pop();int v=nowNode.nowV,w=nowNode.nowW;if(vis[v])continue;vis[v]=1;ans+=w;for(int i=head[v];i;i=e[i].nxt){int nowV=e[i].to;if(!vis[nowV]&&e[i].w<minw[nowV]){minw[nowV]=e[i].w;q.push(Node{nowV,e[i].w});}}}return ans;
}
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addEdge(u,v,w);addEdge(v,u,w);}int ans=prim();printf("%d\n",ans);return 0;
}

 

这篇关于P3366 【模板】最小生成树-Prim的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1099837

相关文章

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

python如何生成指定文件大小

《python如何生成指定文件大小》:本文主要介绍python如何生成指定文件大小的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python生成指定文件大小方法一(速度最快)方法二(中等速度)方法三(生成可读文本文件–较慢)方法四(使用内存映射高效生成

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin(推荐)的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

Java如何根据word模板导出数据

《Java如何根据word模板导出数据》这篇文章主要为大家详细介绍了Java如何实现根据word模板导出数据,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... pom.XML文件导入依赖 <dependency> <groupId>cn.afterturn</groupId>

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤:代码片段:2. 应用 JSON 样式到

SpringBoot实现二维码生成的详细步骤与完整代码

《SpringBoot实现二维码生成的详细步骤与完整代码》如今,二维码的应用场景非常广泛,从支付到信息分享,二维码都扮演着重要角色,SpringBoot是一个非常流行的Java基于Spring框架的微... 目录一、环境搭建二、创建 Spring Boot 项目三、引入二维码生成依赖四、编写二维码生成代码五

Android与iOS设备MAC地址生成原理及Java实现详解

《Android与iOS设备MAC地址生成原理及Java实现详解》在无线网络通信中,MAC(MediaAccessControl)地址是设备的唯一网络标识符,本文主要介绍了Android与iOS设备M... 目录引言1. MAC地址基础1.1 MAC地址的组成1.2 MAC地址的分类2. android与I

PyQt5+Python-docx实现一键生成测试报告

《PyQt5+Python-docx实现一键生成测试报告》作为一名测试工程师,你是否经历过手动填写测试报告的痛苦,本文将用Python的PyQt5和python-docx库,打造一款测试报告一键生成工... 目录引言工具功能亮点工具设计思路1. 界面设计:PyQt5实现数据输入2. 文档生成:python-

Python中Flask模板的使用与高级技巧详解

《Python中Flask模板的使用与高级技巧详解》在Web开发中,直接将HTML代码写在Python文件中会导致诸多问题,Flask内置了Jinja2模板引擎,完美解决了这些问题,下面我们就来看看F... 目录一、模板渲染基础1.1 为什么需要模板引擎1.2 第一个模板渲染示例1.3 模板渲染原理二、模板