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

【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;
}

相关文章:

【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 di…...

第一个 Flask 项目

第一个 Flask 项目 安装环境创建项目启动程序访问项目参数说明Flask对象的初始化参数app.run()参数 应用程序配置参数使用 Flask 的 config.from_object() 方法使用 Flask 的 config.from_pyfile() 方法使用 Flask 的 config.from_envvar() 方法步骤 1: 设置环境变量步骤 2: 编…...

利用 Angular 发挥环境的力量

一.介绍 您是否曾想过如何在不同的环境中为同一应用设置不同的颜色、标题或 API 调用&#xff1f;可以肯定的是&#xff0c;生产 API 和测试 API 是不同的&#xff0c;应谨慎使用。部署时&#xff0c;我们不会在项目的所有地方手动更改所有 API 调用。不应这样做&#xff0c;因…...

Vue3+TypeScript+printjs 实现标签批量打印功能

前言&#xff1a;临时性需求没怎么接触过前端&#xff0c;代码实现有问题及优化点希望大佬可以留言告知一下 开发工具&#xff1a;VS CODE 界面开发&#xff1a;Vue3TypeScriptElementPlus 打印组件&#xff1a;Print-JS 前端打印入口图&#xff1a; 标签页面&#xff1a; …...

微信文件如何直接打印及打印功能在哪里设置?

在数字化时代&#xff0c;打印需求依旧不可或缺&#xff0c;但传统打印店的高昂价格和不便操作常常让人头疼。幸运的是&#xff0c;琢贝打印作为一款集便捷、经济、高效于一体的网上打印平台&#xff0c;正逐渐成为众多用户的首选。特别是通过微信小程序下单&#xff0c;更是让…...

dataX -20240804-master分支

1、相关报错 Error: java.io.IOException: java.lang.RuntimeException: ORC split generation failed with exception: org.apache.orc.impl.SchemaEvolution$IllegalEvolutionException: ORC does not support type conversion from file type struct<nanos:int> (10)…...

【网络】传输层

传输层 一、预备知识1、端口号1、端口号范围划分2、知名端口号3、两个问题4、netstat && iostate5、pidof6、谈下面协议始终铭记两个问题 二、UDP协议&#xff08;简单&#xff09;1、UDP协议端格式2、UDP的特点3、面向数据报4、UDP缓冲区 三、TCP协议&#xff08;重点…...

学生管理系统之更新和删除、筛选

学生管理系统之更新和删除 建立新的窗口 添加组件 进行布局 使用Widget把二个放在一块,作为一列,然后全选进行栅格布局,最后添加弹簧进行微调。 编写增加的槽函数 在主函数中调用对话框...

教您一键批量下载拼多多批发图片信息,节省时间

图片是电商的核心展示手段&#xff0c;高质量、吸引人的图片能显著提升商品吸引力&#xff0c;增强用户体验&#xff0c;促进购买决策。良好的视觉呈现有助于品牌形象的塑造&#xff0c;提高转化率和客户满意度&#xff0c;对电商平台的流量和销售业绩具有直接影响。 使用图快…...

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

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

去噪扩散恢复模型

去噪扩散恢复模型 Bahjat Kawar 计算机科学系 以色列海法理工学院 bahjat.kawarcs.technion.ac.il Michael Elad 计算机科学系 以色列海法理工学院 eladcs.technion.ac.il Stefano Ermon 计算机科学系 美国加利福尼亚州斯坦福大学 ermoncs.stanford.edu …...

Stable Diffusion 官方模型V1.5版本下载

模型描述 Stable Diffusion的官方模型更适合绘制偏写实的风格&#xff0c;如果您想绘制二次元之类的风格&#xff0c;可以考虑下载本站的其它模型。 安装方法 将模型下载后&#xff0c;将会得到一个名为****.ckpt格式的文件&#xff0c;将该文件剪切至你的Stable Diffusion本…...

【算法】双指针-OJ题详解1

双指针-OJ题 移动零&#xff08;点击跳转&#xff09;原理讲解代码实现 复写零&#xff08;点击跳转&#xff09;原理讲解代码实现 快乐数&#xff08;点击跳转&#xff09;原理讲解代码实现 盛最多水的容器&#xff08;点击跳转&#xff09;原理讲解代码实现 有效三角形的个数…...

29 两个任务切换(1)

1 这里涉及到进程的切换与之前的 特权级的切换还是不一样的。 2 给每个进程 在 GDT表中&#xff0c;分配一个 TSS&#xff0c; 这个TSS中 保存着这个进程 所用到的 通用寄存器段寄存器 3个可能的栈&#xff0c; 当进行 进程切换的时候&#xff0c;就是切换到 另一个 TSS表&am…...

正则表达式概述

一、正则表达式概述 正则表达式&#xff08;Regular Expression&#xff0c;简称regex或regexp&#xff09;是一种强大的文本处理工具&#xff0c;它使用一种特定的模式来描述和匹配一系列符合某个句法规则的字符串。在Python中&#xff0c;我们可以使用re模块来操作正则表达式…...

【C语言】Top K问题【建小堆】

前言 TopK问题&#xff1a;从n个数中&#xff0c;找出最大&#xff08;或最小&#xff09;的前k个数。 在我们生活中&#xff0c;经常会遇到TopK问题 比如外卖的必吃榜&#xff1b;成单的前K名&#xff1b;各种数据的最值筛选 问题分析 显然想开出40G的空间是不现实的&#…...

Rust 程序设计语言学习——并发编程

安全且高效地处理并发编程是 Rust 的另一个主要目标。并发编程&#xff08;Concurrent programming&#xff09;&#xff0c;代表程序的不同部分相互独立地执行&#xff0c;而并行编程&#xff08;parallel programming&#xff09;代表程序不同部分同时执行&#xff0c;这两个…...

联邦学习研究综述【联邦学习】

文章目录 0 前言机器学习两大挑战&#xff1a; 1 什么是联邦学习&#xff1f;联邦学习的一次迭代过程如下&#xff1a;联邦学习技术具有以下几个特点&#xff1a; 2 联邦学习的算法原理目标函数本地目标函数联邦学习的迭代过程 3 联邦学习分类横向联邦学习纵向联邦学习联邦迁移…...

深入理解Python中的列表推导式

深入理解Python中的列表推导式 在Python编程中,列表推导式(List Comprehension)是一种简洁而强大的语法,用于创建和操作列表。它不仅提高了代码的可读性,还能显著减少代码的行数。本文将详细介绍什么是列表推导式,如何使用它,以及一些实际应用示例,帮助读者更好地理解…...

Android 实现左侧导航栏:NavigationView是什么?NavigationView和Navigation搭配使用

目录 1&#xff09;左侧导航栏效果图 2&#xff09;NavigationView是什么&#xff1f; 3&#xff09;NavigationView和Navigation搭配使用 4&#xff09;NavigationView的其他方法 一、实现左侧导航栏 由于Android这边没有直接提供左侧导航栏的控件&#xff0c;所以我尝试了…...

如何快速下载拼多多图片信息,效率高

图片是电商吸引顾客的关键因素&#xff0c;高质量的商品图片能提升产品吸引力&#xff0c;增强用户购买欲望。良好的视觉展示有助于建立品牌形象&#xff0c;提高转化率。同时&#xff0c;图片也是商品信息的主要传递媒介&#xff0c;对消费者决策过程至关重要。 使用图快下载器…...

windows 10下,修改ubuntu的密码

(1)在搜索框里面输入cmd&#xff0c;然后点击右键&#xff0c;选择管理员打开 Microsoft Windows [版本 10.0.22631.3880] (c) Microsoft Corporation。保留所有权利。 C:\Windows\System32>C: C:\Windows\System32>cd ../../ C:\>cd Users\ASUS\AppData\Local\Micros…...

【MySQL】慢sql优化全流程解析

定位慢sql 工具排查慢sql 调试工具&#xff1a;Arthas运维工具&#xff1a;Skywalking 通过以上工具可以看到哪个接口比较慢&#xff0c;并且可以分析SQL具体的执行时间&#xff0c;定位到哪个sql出了问题。 启用慢查询日志 慢查询日志记录了所有执行时间超过指定参数(lon…...

RabbitMQ高级特性 - 消息分发(限流、负载均衡)

文章目录 RabbitMQ 消息分发概述如何实现消费分发机制&#xff08;限制每个队列消息数量&#xff09;使用场景限流背景实现 demo 非公平发送&#xff08;负载均衡&#xff09;背景实现 demo RabbitMQ 消息分发 概述 RabbitMQ 的队列在有多个消费者订阅时&#xff0c;默认会通过…...

信号处理——自相关和互相关分析

1.概括 在信号处理中&#xff0c;自相关和互相关是相关分析非常重要的概念&#xff0c;它们能分析一个信号或两个信号在时间维度的相似性&#xff0c;在振动测试分析、雷达测距和声发射探伤得到了广泛的应用。自相关分析的研究对象为一个信号&#xff0c;互相关分析的研究对象…...

如何解决部分设备分辨率不适配

1&#xff09;如何解决部分设备分辨率不适配 2&#xff09;Unity中如何实现草的LOD 3&#xff09;使用了Play Asset Delivery提交版本被Google报错 4&#xff09;如何计算弧线弹道的落地位置 这是第396篇UWA技术知识分享的推送&#xff0c;精选了UWA社区的热门话题&#xff0c;…...

C#插件 调用存储过程(输出参数类型)

存储过程 CREATE PROCEDURE [dbo].[GetSum]num1 INT,num2 INT,result INT OUTPUT AS BEGINselect result num1 num2 END C#代码 using Kingdee.BOS; using Kingdee.BOS.App.Data; using Kingdee.BOS.Core.Bill.PlugIn; using Kingdee.BOS.Util; using System; using System.…...

代码随想录算法训练营day32 | 509. 斐波那契数 、70. 爬楼梯 、746. 使用最小花费爬楼梯

碎碎念&#xff1a;开始动态规划了&#xff01;加油&#xff01; 参考&#xff1a;代码随想录 动态规划理论基础 动态规划常见类型&#xff1a; 动规基础类题目背包问题打家劫舍股票问题子序列问题 解决动态规划问题应该要思考清楚的&#xff1a; 动态规划五部曲&#xff1…...

【人工智能专栏】Learning Rate Decay 学习率衰减

Learning Rate Decay 学习率衰减 使用格式 optimizer = torch.optim.SGD(model.paraters(), lr=0.1, momentum=0.9, weight_decay=1e-4) scheduler = torch.optim...

浙大版《C语言程序设计(第3版)》题目集

练习4-11 统计素数并求和 本题要求统计给定整数M和N区间内素数的个数并对它们求和。 输入格式: 输入在一行中给出两个正整数M和N&#xff08;1≤M≤N≤500&#xff09;。 输出格式: 在一行中顺序输出M和N区间内素数的个数以及它们的和&#xff0c;数字间以空格分隔。 输入…...

关于网站建设的请示范文/最近的热点新闻

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼Language"VBSCRIPT"Sub CATMain()Set documents1 CATIA.DocumentsSet partDocument1 documents1.Add("Part")Set part1 partDocument1.PartSet bodies1 part1.BodiesSet body1 bodies1.Item("零件几…...

网络营销专业的职业生涯规划/百度seo关键词排名优化教程

这些日子我一直在写一个实时操作系统内核&#xff0c;已有小成了&#xff0c;等写完我会全部公开&#xff0c;希望能 够为国内IT的发展尽自己一份微薄的力量。最近看到很多学生朋友和我当年一样没有方向 &#xff0c;所以把我的经历写出来与大家共勉&#xff0c;希望能给刚如行…...

wordpress 农场主题/搜索引擎技巧

目录1、安装pyqt5designer、pyqt52、pycharm中添加外部工具3、使用QtDesigner设计页面1、安装相关库pip install pyqt5designerpip install pyqt52、pycharm添加外部工具在setting中添加两个工具QtDesigner中按照如图填写&#xff1a;Programe&#xff1a;选择designer的安装目…...

wordpress 批量导入 淘宝/软广告经典例子

名称&#xff1a; pwd - print name ofcurrent/working directory 输入当前工作路径 语法&#xff1a; pwd [option] 参数&#xff1a; --help --version 实例&#xff1a; 1)显示当前工作路径 [rootlocalhost ~]# pwd /root 2)显示出软连接的实际目录&#xff0c;而非使用软连…...

网站名称能用商标做名称吗/最热门的短期培训课程

2019独角兽企业重金招聘Python工程师标准>>> 新德汇前端基础框架 v3.0.0 转载于:https://my.oschina.net/miaojiangmin/blog/2254496...

什么网站有教做详情页/免费网站alexa排名查询

铱&#xff08;Iridium&#xff09;&#xff0c;金属元素&#xff0c;元素符号Ir&#xff0c;原子序数77&#xff0c;原子量192.22&#xff0c;元素名来源于拉丁文&#xff0c;原意是“彩虹”。铱在地壳中的含量为千万分之一&#xff0c;常与铂系元素一起分散于冲积矿床和砂积矿…...