当前位置: 首页 > 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;所以我尝试了…...

STM32与W25Q64:构建自定义上位机字库烧录系统的实践指南

1. 为什么需要自定义字库烧录系统 在嵌入式显示项目中&#xff0c;中文字库的处理一直是个头疼的问题。我去年接手一个工业HMI项目&#xff0c;客户要求设备能显示繁简体中文、日文和部分特殊符号。最初尝试用SD卡加载字库&#xff0c;结果现场有30%的设备因为SD卡接触不良导致…...

收藏!国内大厂大模型人才招聘真相,小白/程序员入门必看

在大模型技术飞速迭代的当下&#xff0c;国内各大互联网大厂对大模型高端人才的投入力度已然拉满&#xff0c;几乎每家头部企业都推出了针对顶尖人才的专项招聘计划&#xff0c;而这些计划的核心共性&#xff0c;就是“高薪兜底”搭配“高门槛筛选”&#xff0c;成为行业内最引…...

LeaguePrank:5分钟学会英雄联盟个性化美化工具终极指南 [特殊字符]

LeaguePrank&#xff1a;5分钟学会英雄联盟个性化美化工具终极指南 &#x1f3ae; 【免费下载链接】LeaguePrank 项目地址: https://gitcode.com/gh_mirrors/le/LeaguePrank 想要在英雄联盟中展示与众不同的个人形象吗&#xff1f;LeaguePrank 正是你需要的个性化美化工…...

建立情感绑架链:让团队恐惧失去你——软件测试从业者的职场影响力解析

测试工程师的隐形权力困境 在软件研发体系中&#xff0c;测试工程师常陷入价值被低估的困境。当迭代压力激增时&#xff0c;测试周期首当其冲被压缩&#xff1b;当线上出现故障时&#xff0c;测试环节却成为追责焦点。这种结构性矛盾催生出一种特殊的职场生存策略——通过构建…...

保姆级教程:在Windows上用CMake+QT给CloudCompare 2.13.x添加一个Standard插件(附OpenCV配置)

从零构建CloudCompare插件&#xff1a;Windows平台CMakeQT全流程实战指南 在三维点云处理领域&#xff0c;CloudCompare凭借其开源特性和丰富的插件生态&#xff0c;已成为研究人员和工程师的首选工具之一。但对于刚接触插件开发的初学者而言&#xff0c;从环境配置到成功编译第…...

绝区零一条龙自动化工具:从机械操作到智能游戏的进化指南

绝区零一条龙自动化工具&#xff1a;从机械操作到智能游戏的进化指南 【免费下载链接】ZenlessZoneZero-OneDragon 绝区零 一条龙 | 全自动 | 自动闪避 | 自动每日 | 自动空洞 | 支持手柄 项目地址: https://gitcode.com/gh_mirrors/ze/ZenlessZoneZero-OneDragon 当你第…...

P1122 最大子树和

题目描述 小明对数学饱有兴趣&#xff0c;并且是个勤奋好学的学生&#xff0c;总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课&#xff0c;路上见到一个老伯正在修剪花花草草&#xff0c;顿时想到了一个有关修剪花卉的问题。于是当日课后&#xff0c;小明就向老…...

Baseweb表单文件上传组件:从基础到拖拽上传的完整指南

Baseweb表单文件上传组件&#xff1a;从基础到拖拽上传的完整指南 【免费下载链接】baseweb A React Component library implementing the Base design language 项目地址: https://gitcode.com/gh_mirrors/ba/baseweb Baseweb是一个基于React的企业级UI组件库&#xff…...

计算机网络学习笔记】初始网络之网络发展和OSI七层模型

以下是基于 Python Pygame 实现的完整俄罗斯方块游戏代码&#xff0c;包含核心功能&#xff08;方块生成、移动、旋转、消除、计分&#xff09;&#xff0c;注释详细可直接运行&#xff1a;第一步&#xff1a;安装依赖先安装 Pygame 库&#xff1a; pip install pygame 第二步…...

施密特触发器除了整形还能干啥?聊聊它在Arduino按键消抖和信号调理里的妙用

施密特触发器在Arduino中的高阶应用&#xff1a;从按键消抖到信号调理的实战指南 当你在调试Arduino项目时&#xff0c;是否遇到过按键响应不稳定、传感器读数跳变的问题&#xff1f;这些看似简单的硬件问题&#xff0c;往往会让开发者花费大量时间在软件滤波上。实际上&#x…...