【刷题】图论——最小生成树:Prim、Kruskal【模板】
假设有n个点m条边。
Prim适用于邻接矩阵存的稠密图,时间复杂度是 O ( n 2 ) O(n^2) O(n2),可用堆优化成 O ( n l o g n ) O(nlogn) O(nlogn)。
Kruskal适用于稀疏图,n个点m条边,时间复杂度是 m l o g ( m ) mlog(m) mlog(m)。
Prim:遍历n次,每次选择连通块和外面的点到连通块距离最短的一条边,并将该边对应点加入连通块中,更新其他店到连通块的距离
Kruskal:将所有边权从小到大排序,依次枚举每条边(a和b相连,边权w),如果发现目前a和b不在一个连通块内,将a和b加入连通块中。
题目

题目链接
Prim
#include <iostream>
#include <cstring>using namespace std;
const int N = 110;
int n;
int w[N][N];
int dist[N]; // 外界每个点和当前连通块直接相连的边的最小值
bool st[N]; // 是否加入连通块int prim() {int res = 0;memset(dist, 0x3f, sizeof(dist));dist[1] = 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])) { // j不在连通块里且或j距离更小t = j;}}res += dist[t];st[t] = true;for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]); // 更新所有t能到的距离}return res;
}
int main() {scanf("%d", &n);for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= n; j ++ ) {scanf("%d", &w[i][j]);}}cout << prim() << endl;
}
Kruskal
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 110;
const int M = 10010;struct Edge {int a, b, w;bool operator< (const Edge &t) const {return w < t.w;}
};Edge e[M];
int p[N];
int n, w, m;int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}
int kruskal() {for (int i = 1; i <= n; i ++ ) p[i] = i;sort(e, e + m);int res = 0;for (int i = 0; i < m; i ++ ) {int a = find(e[i].a);int b = find(e[i].b);if (a != b) {p[a] = b;res += e[i].w;}}return res;
}
int main() {scanf("%d", &n);m = n * n;for (int i = 0; i < n; i ++ ) {for (int j = 0; j < n; j ++ ) {scanf("%d", &w);e[i * n + j] = {i + 1, j + 1, w};}}cout << kruskal() << endl;
}
相关文章:
【刷题】图论——最小生成树:Prim、Kruskal【模板】
假设有n个点m条边。 Prim适用于邻接矩阵存的稠密图,时间复杂度是 O ( n 2 ) O(n^2) O(n2),可用堆优化成 O ( n l o g n ) O(nlogn) O(nlogn)。 Kruskal适用于稀疏图,n个点m条边,时间复杂度是 m l o g ( m ) mlog(m) mlog(m)。 Pr…...
使用uniapp实现小程序获取wifi并连接
Wi-Fi功能模块 App平台由 uni ext api 实现,需下载插件:uni-WiFi 链接:https://ext.dcloud.net.cn/plugin?id10337 uni ext api 需 HBuilderX 3.6.8 iOS平台获取Wi-Fi信息需要开启“Access WiFi information”能力登录苹果开发者网站&…...
回忆杀之手搓当年搓过的Transformer
整体代码 import mathimport paddle import paddle.nn as nn import paddle.nn.functional as Fclass MaskMultiHeadAttention(nn.Layer):def __init__(self, hidden_size, num_heads):super(MaskMultiHeadAttention, self).__init__()assert hidden_size % num_heads 0, &qu…...
【AR】使用深度API实现虚实遮挡
遮挡效果 本段描述摘自 https://developers.google.cn/ar/develop/depth 遮挡是深度API的应用之一。 遮挡(即准确渲染虚拟物体在现实物体后面)对于沉浸式 AR 体验至关重要。 参考下图,假设场景中有一个Andy,用户可能需要放置在包含…...
python-pytorch实现skip-gram 0.5.001
python-pytorch实现skip-gram 0.5.000 数据加载、切词准备训练数据准备模型和参数训练保存模型加载模型简单预测获取词向量画一个词向量的分布图使用词向量计算相似度参考数据加载、切词 按照链接https://blog.csdn.net/m0_60688978/article/details/137538274操作后,可以获得…...
C语言:约瑟夫环问题详解
前言 哈喽,宝子们!本期为大家带来一道C语言循环链表的经典算法题(约瑟夫环)。 目录 1.什么是约瑟夫环2.解决方案思路3.创建链表头结点4.创建循环链表5.删除链表6.完整代码实现 1.什么是约瑟夫环 据说著名历史学家Josephus有过以下…...
【刷题篇】回溯算法(二)
文章目录 1、求根节点到叶节点数字之和2、二叉树剪枝3、验证二叉搜索树4、二叉搜索树中第K小的元素5、二叉树的所有路径 1、求根节点到叶节点数字之和 给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表…...
Windows系统本地部署Jupyter Notebook并实现公网访问编辑笔记
文章目录 1.前言2.Jupyter Notebook的安装2.1 Jupyter Notebook下载安装2.2 Jupyter Notebook的配置2.3 Cpolar下载安装 3.Cpolar端口设置3.1 Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 在数据分析工作中,使用最多的无疑就是各种函数、图表、…...
自动化运维(二十七)Ansible 实战Shell 插件和模块工具
Ansible 支持多种类型的插件,这些插件可以帮助你扩展和定制 Ansible 的功能。每种插件类型都有其特定的用途和应用场景。今天我们一起学习Shell 插件和模块工具。 一、 Shell 插件 Ansible shell 插件决定了 Ansible 如何在远程系统上执行命令。这些插件非常关键&a…...
Jenkins使用-绑定域控与用户授权
一、Jenkins安装完成后,企业中使用,首先需要绑定域控以方便管理。 操作方法: 1、备份配置文件,防止域控绑定错误或授权策略选择不对,造成没办法登录,或登录后没有权限操作。 [roottest jenkins]# mkdir ba…...
【前端】es-drager 图片同比缩放 缩放比 只修改宽 只修改高
【前端】es-drager 图片同比缩放 缩放比 ES Drager 拖拽组件 (vangleer.github.io) 核心代码 //初始宽 let width ref(108)//初始高 let height ref(72)//以下两个变量 用来区分是单独的修改宽 还是高 或者是同比 //缩放开始时的宽 let oldWidth 0 //缩放开始时的高 let o…...
蓝桥杯第十四届蓝桥杯大赛软件赛省赛C/C++ 大学 A 组题解
1.幸运数 题目链接:0幸运数 - 蓝桥云课 (lanqiao.cn) #include<bits/stdc.h> using namespace std; bool deng(string& num){int n num.size();int qian 0,hou 0;for(int i0;i<n/2;i) qian (num[i]-0);for(int in/2;i<n;i) hou (num[i]-0);r…...
eclipse .project
.project <?xml version"1.0" encoding"UTF-8"?> <projectDescription> <name>scrm-web</name> <comment></comment> <projects> </projects> <buildSpec> <buil…...
react的闭包陷阱
React 的闭包陷阱是指在使用 React Hooks 时,由于闭包特性导致在某些函数或异步操作中无法正确访问到更新后状态或 prop 的值,而仍旧使用了旧值。下面通过几个代码示例来具体说明闭包陷阱的几种常见情形: 示例 1: useState 闭包陷阱 import…...
神经网络解决回归问题(更新ing)
神经网络应用于回归问题 优势是什么???生成数据集:通用神经网络拟合函数调整不同参数对比结果初始代码结果调整神经网络结构调整激活函数调整迭代次数增加早停法变量归一化处理正则化系数调整学习率调整 总结ingfnn.py进行计算&am…...
【小红书校招场景题】12306抢票系统
1 坐过高铁吧,有抢过票吗。你说说抢票系统对于后端开发人员而言会有哪些情况? 对于后端开发人员来说,开发和维护一个高铁抢票系统(如中国的12306)会面临一系列的挑战和情况。这些挑战主要涉及系统的性能、稳定性、数据…...
Spring(三)
1. Spring单例Bean是不是线程安全的? Spring单例Bean默认并不是线程安全的。由于多个线程可能访问同一份Bean实例,当Bean的内部包含了可变状态(mutable state)即有可修改的成员变量时,就可能出现线程安全问题。Spring容器不会自动…...
使用element-plus中的表单验证
标签页代码如下: // 注意:el-form中的数据绑定不可以用v-model,要使用:model <el-form ref"ruleFormRef" :rules"rules" :model"userTemp" label-width"80px"><el-row :gutter"20&qu…...
flinksql
Flink SQL 是 Apache Flink 项目中的一个重要组成部分,它允许开发者使用标准的 SQL 语言来处理流数据和批处理数据。Flink SQL 提供了一种声明式的编程范式,使得用户能够以一种简洁、高效且易于理解的方式来表达复杂的数据处理逻辑。 ### 背景 Flink SQL 的设计初衷是为了简…...
Dockerfile中 CMD和ENTRYPOINT的区别
在 Dockerfile 中,CMD 和 ENTRYPOINT 都用于指定容器启动时要执行的命令。它们之间的主要区别是: - CMD 用于定义容器启动时要执行的命令和参数,它设置的值可以被 Dockerfile 中的后续指令覆盖,包括在运行容器时传递的参数。如果…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
高防服务器价格高原因分析
高防服务器的价格较高,主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因: 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器,因此…...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...
归并排序:分治思想的高效排序
目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法,由约翰冯诺伊曼在1945年提出。其核心思想包括: 分割(Divide):将待排序数组递归地分成两个子…...
