【C++学习第19天】最小生成树(对应无向图)

一、最小生成树

二、代码

1、Prim算法

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 510, INF = 0x3f3f3f3f;int n, m;
int g[N][N];
int dist[N];
bool st[N];int prim()
{memset(dist, 0x3f, sizeof dist);int res = 0;for(int i = 0; i < n; i++){int t = -1;for(int j = 1; j <= n; j++)if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;if(i && dist[t] == INF)return INF;if(i)res += dist[t];for(int j = 1; j <= n; j++)dist[j] = min(dist[j], g[t][j]);st[t] = true;}return res;
}int main()
{scanf("%d%d", &n, &m);memset(g, 0x3f, sizeof g);while(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = g[b][a] = min(g[a][b], c);}int t = prim();if(t == INF)puts("impossible");elseprintf("%d\n", t);return 0;
}

2、Kruskal算法

#include <iostream>
#include <algorithm>using namespace std;const int N = 200010;int n, m;
int p[N];struct Edge
{int a, b, w;bool operator< (const Edge &W) const{return w < W.w;}
}edges[N];int find(int x)
{if(p[x] != x)p[x] = find(p[x]);return p[x];
}int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < m; i++){int a, b, w;scanf("%d%d%d", &a, &b, &w);edges[i] = {a, b, w};}sort(edges, edges + m);for(int i = 1; i <= n; i++)p[i] = i;int res = 0, cnt = 0;for(int i = 0; i < m; i++){int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a), b = find(b);if(a != b){p[a] = b;res += w;cnt++;}}if(cnt < n - 1)puts("impossible");elseprintf("%d\n", res);return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

学习分享:解析电商 API 接入的技术重难点及解决方案

在当今电商业务迅速发展的时代&#xff0c;接入电商 API 已成为许多企业提升竞争力和拓展业务的重要手段。然而&#xff0c;在这个过程中&#xff0c;往往会遇到一系列的技术重难点。本文将深入解析这些问题&#xff0c;并提供相应的解决方案。 一、电商 API 接入的技术重难点 …

c++ 初始值设定项列表(initializer_list)

引例 我们在写c代码的时候&#xff0c;多多少少会遇到这样写的&#xff1a; 如果是这样写还好说&#xff1a; 第一个是因为编译器强制匹配参数。 其他都是因为在有对应构造函数的情况下支持的隐式类型转换。 而支持的构造函数是这个&#xff1a; 如果有不懂的可以开这一篇&a…

麦田物语第十八天

系列文章目录 麦田物语第十八天 文章目录 系列文章目录一、(Editor)制作 [SceneName] Attribute 特性二、场景切换淡入淡出和动态 UI 显示一、(Editor)制作 [SceneName] Attribute 特性 在本节课我们编写Unity的特性Attribute来更好的完善我们项目,具体是什么呢,就是当…

深入理解 ReLU 激活函数及其在深度学习中的应用【激活函数、Sigmoid、Tanh】

ReLU&#xff08;Rectified Linear Unit&#xff09;激活函数 ReLU&#xff08;Rectified Linear Unit&#xff09;激活函数是一种广泛应用于神经网络中的非线性激活函数。其公式如下&#xff1a; ReLU ( x ) max ⁡ ( 0 , x ) \text{ReLU}(x) \max(0, x) ReLU(x)max(0,x) 在…

docker部署elasticsearch和Kibana

部署elasticsearch 通过下面的Docker命令即可安装单机版本的elasticsearch&#xff1a; docker run -d \--name es \-e "ES_JAVA_OPTS-Xms512m -Xmx512m" \-e "discovery.typesingle-node" \-v es-data:/usr/share/elasticsearch/data \-v es-plugins:/u…

《LeetCode热题100》---<5.①普通数组篇五道>

本篇博客讲解LeetCode热题100道普通数组篇中的五道题 第一道&#xff1a;最大子数组和&#xff08;中等&#xff09; 第二道&#xff1a;合并区间&#xff08;中等&#xff09; 第一道&#xff1a;最大子数组和&#xff08;中等&#xff09; 法一&#xff1a;贪心算法 class So…

我的256天创作纪念日

机缘 ————今天一大早收到CSDN的推送消息&#xff0c;告诉我这是我的256天创作纪念日。在这个特别的日子里&#xff0c;我回望自己踏上创作之路的点点滴滴&#xff0c;心中充满了感慨与感激。从最初的懵懂尝试到如今能够自信地分享见解&#xff0c;这段旅程不仅见证了我的成…

【教学类-73-01】20240804镂空瓶子01

背景需求&#xff1a; 瓶子里的春天呀&#xff01; - 小红书 (xiaohongshu.com)https://www.xiaohongshu.com/explore/63ef87f8000000000703acae?app_platformandroid&ignoreEngagetrue&app_version8.47.0&share_from_user_hiddentrue&xsec_sourceapp_share&…

揭秘Matplotlib等高线图:让数据‘高山流水‘间,笑点与深度并存!

1. 引言 在这个数据如山的时代&#xff0c;你是不是也曾在茫茫数海中迷失方向&#xff0c;渴望找到那片隐藏的“数据绿洲”&#xff1f;别怕&#xff0c;今天咱们就来聊聊Matplotlib这位绘图界的魔术师&#xff0c;特别是它那令人叹为观止的等高线图技能。想象一下&#xff0c…

MySQL:数据库用户

数据库用户 在关系型数据库管理系统中&#xff0c;数据库用户&#xff08;USER&#xff09;是指具有特定权限和访问权限的登录账户。每个用户都有自己的用户名和密码&#xff0c;以便系统可以通过认证来识别他们的身份。数据库用户可以登录数据库&#xff0c;在其中执行各种类…

【QT】常用控件-上

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 目录 &#x1f449;&#x1f3fb;QWidgetenabledgeometryrect制作上下左右按钮 window frame 的影响window titlewindowIcon代码示例: 通过 qrc 管理图片作为图标 windowOpacitycursor使用qrc自…

【论文笔记】SEED: A Simple and Effective 3D DETR in Point Clouds

原文链接&#xff1a;https://arxiv.org/abs/2407.10749 简介&#xff1a;基于DETR的3D点云检测器难以达到较高的性能&#xff0c;这可能有两个原因&#xff1a;&#xff08;1&#xff09;由于点云的稀疏性和分布不均匀&#xff0c;获取合适的物体查询较为困难&#xff1b;&…

基于微信小程序的微课堂笔记的设计与实现(源码+论文+部署讲解等)

博主介绍&#xff1a;✌全网粉丝10W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌ 技术栈介绍&#xff1a;我是程序员阿龙&#xff…

给虚拟机Ubuntu扩展硬盘且不丢数据

1.Ubuntu关机状态下先扩展&#xff0c;如扩展20GB 2.进入ubuntu&#xff0c;切换root登录&#xff0c;必须是root全选&#xff0c;否则启动不了分区工具gparted 将新的20GB创建好后&#xff0c;选择ext4,primary&#xff1b; 3.永久挂载 我的主目录在/并挂载到/dev/sda1 从图…

【C++】C++11之新的类功能与可变参数模板

目录 一、新的默认成员函数 二、新的关键字 2.1 default 2.2 detele 2.3 final和override 三、可变参数模板 3.1 定义 3.2 递归展开参数包 3.3 逗号表达式展开参数包 3.4 emplace_back 一、新的默认成员函数 在C11之前&#xff0c;默认成员函数只有六个&#xff0c;…

【机器学习算法基础】(基础机器学习课程)-11-k-means-笔记

示例案例 为了更好地理解 K-Means 算法&#xff0c;下面通过一个简单的案例进行说明。 假设我们有以下 10 个二维数据点&#xff0c;表示不同商店的销售额&#xff08;单位&#xff1a;千元&#xff09;和顾客数&#xff08;单位&#xff1a;人&#xff09;&#xff1a; [(1…

常见cms漏洞之dedecms

DedeCMS是织梦团队开发PHP 网站管理系统&#xff0c;它以简单、易用、高效为特色&#xff0c;组建出各种各样各具特色的网站&#xff0c;如地方门户、行业门户、政府及企事业站点等。 下载地址请网上自行寻找 搭建方式选择php study 首先搭建环境 #前台http://localhost/dedecm…

Java AI伪原创视频创作视频提取文案改写去水印系统小程序源码

&#x1f525;AI赋能创作新纪元&#xff01;伪原创视频文案提取改写去水印全能系统大揭秘 &#x1f680; 开篇&#xff1a;创意无界&#xff0c;AI来助力 在这个视觉盛行的时代&#xff0c;视频创作成为了表达自我、传递信息的重要方式。但你是否曾为寻找灵感、撰写文案、处理…

sa-token登录机制以及网关统一鉴权环境搭建

文章目录 1.sa-token1.37集成&#xff08;基于token&#xff09;1.文档网址2.**sun-club-auth-application-controller引入依赖**3.application.yml4.sun-club-auth-application-controller测试的controller1.UserController.java2.启动测试1.登录&#xff0c;得到satoken2.验证…

【FPGA】cordic算法实现三角函数

参考资料&#xff1a;https://zhuanlan.zhihu.com/p/638520243https://zhuanlan.zhihu.com/p/638520243