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

OpenClaw学术研究助手:Qwen3-32B驱动的论文摘要与笔记整理

OpenClaw学术研究助手&#xff1a;Qwen3-32B驱动的论文摘要与笔记整理 1. 为什么需要本地化的AI研究助手&#xff1f; 去年冬天&#xff0c;我在整理一个跨学科研究项目的文献时陷入了困境。手头堆积了200多篇PDF论文&#xff0c;每篇都需要提取核心观点、记录关键数据&#…...

Llama-3.2V-11B-cot部署教程:双卡4090一键启动视觉推理工具

Llama-3.2V-11B-cot部署教程&#xff1a;双卡4090一键启动视觉推理工具 1. 项目概述 Llama-3.2V-11B-cot是基于Meta多模态大模型开发的高性能视觉推理工具&#xff0c;专为双卡4090环境优化。它解决了传统大模型部署复杂、视觉权重加载失败等痛点&#xff0c;让普通用户也能轻…...

深度解析开源工具如何实现游戏性能优化:Genshin FPS Unlocker专业实战指南

深度解析开源工具如何实现游戏性能优化&#xff1a;Genshin FPS Unlocker专业实战指南 【免费下载链接】genshin-fps-unlock unlocks the 60 fps cap 项目地址: https://gitcode.com/gh_mirrors/ge/genshin-fps-unlock Genshin FPS Unlocker 是一款专注于游戏性能优化的…...

51单片机按键控制实战:从消抖到状态切换的完整代码解析

51单片机按键控制实战&#xff1a;从消抖到状态切换的完整代码解析 在嵌入式系统开发中&#xff0c;按键控制是最基础也最关键的交互方式之一。无论是简单的家电控制面板&#xff0c;还是复杂的工业设备操作界面&#xff0c;按键作为人机交互的桥梁&#xff0c;其稳定性和响应速…...

造相-Z-Image效果对比:Z-Image在中文语义理解准确率上超越SDXL实测

造相-Z-Image效果对比&#xff1a;Z-Image在中文语义理解准确率上超越SDXL实测 最近在折腾本地文生图&#xff0c;发现了一个挺有意思的现象。我用的是基于通义千问官方Z-Image模型定制的“造相-Z-Image”引擎&#xff0c;专门为我的RTX 4090显卡做了优化。本来只是想试试它的…...

OpenClaw关键词挖掘Agent配置(附SOP脚本,可直接复制使用)

OpenClaw关键词挖掘Agent全栈配置指南&#xff08;附可执行SOP脚本&#xff09;一、系统架构解析OpenClaw关键词挖掘系统采用分布式架构&#xff0c;核心由以下模块构成&#xff1a;数据采集层实时爬虫引擎&#xff1a;支持动态IP代理&#xff0c;突破反爬限制API集成模块&…...

检索大赛 实验4 文心4.5结果

根据对上述文献的逐一核实&#xff08;通过Google Scholar、会议官网、期刊数据库及作者主页查询&#xff09;&#xff0c;真实存在的文献如下&#xff1a;---### **真实存在的文献**1. **"VulBERTa: A Pre-Trained Language Model for Software Vulnerability Identifica…...

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

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

Android定位模拟技术全解析:基于系统级Hook的位置伪造实现方案

Android定位模拟技术全解析&#xff1a;基于系统级Hook的位置伪造实现方案 【免费下载链接】FakeLocation Xposed module to mock locations per app. 项目地址: https://gitcode.com/gh_mirrors/fak/FakeLocation 在移动应用开发与测试过程中&#xff0c;精准控制定位信…...

隐私优先的WiFi人体姿态追踪:RuView如何用无线信号“看见“人体

隐私优先的WiFi人体姿态追踪&#xff1a;RuView如何用无线信号"看见"人体 【免费下载链接】RuView Production-ready implementation of InvisPose - a revolutionary WiFi-based dense human pose estimation system that enables real-time full-body tracking thr…...