【刷题】图论——最小生成树: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 中的后续指令覆盖,包括在运行容器时传递的参数。如果…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
