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

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...