C语言-算法-最小生成树
【模板】最小生成树
题目描述
如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz。
输入格式
第一行包含两个整数 N , M N,M N,M,表示该图共有 N N N 个结点和 M M M 条无向边。
接下来 M M M 行每行包含三个整数 X i , Y i , Z i X_i,Y_i,Z_i Xi,Yi,Zi,表示有一条长度为 Z i Z_i Zi 的无向边连接结点 X i , Y i X_i,Y_i Xi,Yi。
输出格式
如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
样例 #1
样例输入 #1
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
样例输出 #1
7
提示
数据规模:
对于 20 % 20\% 20% 的数据, N ≤ 5 N\le 5 N≤5, M ≤ 20 M\le 20 M≤20。
对于 40 % 40\% 40% 的数据, N ≤ 50 N\le 50 N≤50, M ≤ 2500 M\le 2500 M≤2500。
对于 70 % 70\% 70% 的数据, N ≤ 500 N\le 500 N≤500, M ≤ 1 0 4 M\le 10^4 M≤104。
对于 100 % 100\% 100% 的数据: 1 ≤ N ≤ 5000 1\le N\le 5000 1≤N≤5000, 1 ≤ M ≤ 2 × 1 0 5 1\le M\le 2\times 10^5 1≤M≤2×105, 1 ≤ Z i ≤ 1 0 4 1\le Z_i \le 10^4 1≤Zi≤104。
样例解释:

所以最小生成树的总边权为 2 + 2 + 3 = 7 2+2+3=7 2+2+3=7。
代码
#include <stdio.h>
#include <stdlib.h>
#define MAXN 300000
#define MAXM 300000
typedef struct // 定义边的结构体
{int u, v, w;
}Edge;
Edge edges[MAXM]; // 存储所有的边
int pa[MAXN]; // 并查集数组,用于判断两个节点是否在同一棵树中
int N, M; // N是节点数,M是边数
int cmp(Edge a, Edge b); // 边的比较函数,按照边的权重从小到大排序
int find(int x); // 并查集的查找函数,用于查找节点x的根节点
int kruskal(); // Kruskal算法函数int main(int argc, char *argv[])
{int i;scanf("%d %d", &N, &M); // 读取节点数和边数for (i = 0; i < M; i++){scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);}int res = kruskal(); // 调用Kruskal算法计算最小生成树的权重if (res == -1) // 如果图不连通{printf("orz\n");}else{printf("%d\n", res);}return 0;
}int cmp(Edge a, Edge b) // 边的比较函数,按照边的权重从小到大排序
{return (a.w - b.w);
}int find(int x) // 并查集的查找函数,用于查找节点x的根节点
{while (pa[x] != x){x = pa[x];}return x;
}int kruskal() // Kruskal算法函数
{int i, j;for (i = 0; i < M; i++) // 将所有的边按照从小到大排序{for (j = i + 1; j < M; j++){if (cmp(edges[i], edges[j]) > 0){Edge temp = edges[i];edges[i] = edges[j];edges[j] = temp;}}}for (i = 1; i <= N; i++) // 初始化并查集{pa[i] = i;}int res = 0; // 存储最小生成树的权重int cnt = 0; // 存储当前已经选择的边的数量for (i = 0; i < M; i++) // 遍历所有的边{int u = find(edges[i].u); // 边的一个节点int v = find(edges[i].v); // 边的另一个节点// 如果两个节点不在同一棵树中,说明这条边可以添加到最小生成树中if (u != v){res += edges[i].w; // 更新最小生成树的权重pa[u] = v; // 合并两棵树cnt++; // 更新已经选择的边的数量}}if (cnt != N - 1) // 如果选择边的数量小于N - 1,说明图不连通{return -1;}return res; // 返回最小生成树的权重
}
相关文章:
C语言-算法-最小生成树
【模板】最小生成树 题目描述 如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz。 输入格式 第一行包含两个整数 N , M N,M N,M,表示该图共有 N N N 个结点和 M M M 条无向边。 接下来 M M M 行…...
android 扫描某个包下的所有类
注意事项 如果在用Android Studio开发过程中,如果新增了类,扫描不到。只能把APP卸载了,才能扫描到。 可能是Instance Run 的影响。 后面研究一下这篇文章,看看能不能解决 Android 遍历Apk下的所有类文件 package com.trs.nmip.…...
远程ssh 不通的原因之一
背景:我都想大喊一声,我上网是通的, ping网址是通的,ping www.baidu.com 是通的, 怎么都远程不了,报超时;嘿, 别人远程就能行。我都想挠头了。 目录 1. 先 ping 自己,…...
wamp集成环境部署
Windows下Apache服务器搭建 第一步:下载Windows下的最新ZIP压缩包 推荐下载网址:http://www.apachelounge.com/download/ 为了让Apache服务器发挥更好的性能,请根据自己的系统选择下载,如果不清楚自己的系统是64位还是32位&am…...
使用antd design pro 及后端nodejs express 结合minio进行文件的上传和下载管理
使用Ant Design Pro前端框架结合Node.js Express后端服务以及MinIO作为对象存储,实现文件上传和下载管理的基本步骤如下: 1. 安装所需依赖 在Node.js Express项目中安装minio客户端库: npm install minio --save 在前端项目(假…...
Unity常用的优化技巧集锦
Unity性能优化是面试的时候经常被问道的一些内容,今天给大家分享一些常用的Unity的优化技巧和思路,方便大家遇到问题时候参考与学习。 对啦!这里有个游戏开发交流小组里面聚集了一帮热爱学习游戏的零基础小白,也有一些正在从事游…...
c++动态调用dll
在C中动态调用DLL(动态链接库)可以使用Windows API函数。以下是一个简单的示例,演示如何动态加载和调用DLL中的函数: #include <windows.h> #include <iostream>int main() { // 加载DLL HMODULE hModule LoadLibrar…...
使用Python自动化操作手机,自动执行常见任务,例如滑动手势、呼叫、发送短信等等
使用Python自动化操作手机,自动执行常见任务,例如滑动手势、呼叫、发送短信等等。 此自动化脚本将帮助你使用 Python 中的 Android 调试桥 (ADB) 自动化你的智能手机。下面我将展示如何自动执行常见任务,例如滑动手势、呼叫、发送短信等等。 您可以了解有关 ADB 的更多信息,…...
E - Souvenir(图论典型例题)
思路:对于有很多询问的题,一般都是先初始化。我们求出每个点到其他点的最短路径以及相同路径下最大的价值和即可。 代码: #include <bits/stdc.h> #define pb push_back #define a first #define b second using namespace std; type…...
【SpringBoot篇】添加富文本编辑器操作
文章目录 🍔使用步骤⭐首先我们需要安装富文本编辑器⭐在<script>中引入富文本编辑器⭐富文本图片上传接口⭐初始化富文本编辑器⭐调用 初始化富文本编辑器的方法🎈新增🎈编辑🎈保存 ⭐添加按钮⭐实现viewEditor函数&#x…...
前台vue配置
前台 vue环境 1.傻瓜式安装node: 官网下载:https://nodejs.org/zh-cn/2.安装cnpm: >: npm install -g cnpm --registryhttps://registry.npm.taobao.org3.安装vue最新脚手架: >: cnpm install -g vue/cli注:如果2、3步报错,清除缓…...
牛客周赛 Round 18 解题报告 | 珂学家 | 分类讨论计数 + 状态DP
前言 整体评价 前三题蛮简单的,T4是一个带状态的DP,这题如果用背包思路去解,不知道如何搞,感觉有点头痛。所以最后还是选择状态DP来求解。 欢迎关注 珂朵莉 牛客周赛专栏 珂朵莉 牛客小白月赛专栏 A. 游游的整数翻转 这题最好…...
CentOS防火墙基本操作
CentOS操作系统中的防火墙可以使用firewalld或iptables来进行配置。 firewalld(默认): 查看当前状态:systemctl status firewalld 开启/关闭防火墙服务:sudo systemctl start/stop firewalld 设置开机自动启动/不启…...
Shell脚本的编程规范和变量类型
一. 了解编程 1.程序编程风格 面向过程语言 开发的时候 需要一步一步执行 问题规模小,可以步骤化,按部就班处理 以指令为中心,数据服务于指令 C,shell 面向对象语言 开发的时候 将任务当成一个整体 将编程看成是一个…...
C++面试:跳表
目录 跳表介绍 跳表的特点: 跳表的应用场景: C 代码示例: 跳表的特性 跳表示例 总结 跳表(Skip List)是一种支持快速搜索、插入和删除的数据结构,具有相对简单的实现和较高的查询性能。下面是跳表…...
掌握C++20的革命性特性:Concepts
掌握C20的革命性特性:Concepts C20 的新特性 C20 引入了 Concepts,这是一种用于限制类和函数模板的模板类型和非类型参数的命名要求。Concepts 是作为编译时评估的谓词,用于验证传递给模板的模板参数。Concepts 的主要目的是使模板相关的编…...
win11开机后频繁刷新桌面,任务栏不显示,文件资源管理器explorer报错ntdll.dll
win11 开机后桌面频繁刷新,cpu 暴涨,任务栏不出现。 不知道是安装了什么软件还是系统升级造成的,好长时间不重启电脑了,然后重启了下电脑。 结果就是: 现象描述 重启后 输入密码进入后 变得巨慢。好久才进入的桌面。…...
解决Git添加.gitignore文件后不生效的问题
1. 问题描述 如上图所示,在已存在.gitignore文件且已经提交过的Git管理的项目中,其中.class、.jar文件以及.idea目录内的内容全部都还是被Git管理了,可见.gitignore文件并没有生效。 2. 原因发现 .gitignore文件只能作用于 Untracked Files…...
Shell Linux学习笔记
注意:该文章摘抄之百度,仅当做学习笔记供小白使用,若侵权请联系删除! 目录 什么是shell ? Linux正则匹配 grep tar与unzip echo history 重定向 shell 单双引号 位置参数 预定义变量 运算 正则表达式 字符截取命令 …...
kingbase常用SQL总结之锁等待信息
锁信息与等待事件 分析kingbase(pg)数据库锁等待、死锁时需要我们准确的定位等锁或者死锁相关的事务。关于获取锁等待信息或者死锁信息已有经典的SQL可以直接使用,但是需要我们先了解sql语句获取的每个字段的意义。 获取到锁等待事务不能完全…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
