当前位置: 首页 > news >正文

acwing算法提高之图论--最小生成树的典型应用

目录

  • 1 介绍
  • 2 训练

1 介绍

本专题用来记录使用prim算法或kruskal算法求解的题目。

2 训练

题目1:1140最短网络

C++代码如下,

#include <iostream>
#include <cstring>using namespace std;const int N = 110, INF = 0x3f3f3f3f;
int g[N][N];
int d[N];
bool st[N];
int n, m;void prim() {memset(d, 0x3f, sizeof d);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 || d[t] > d[j])) {t = j;}}st[t] = true;if (i) res += d[t];for (int j = 1; j <= n; ++j) {if (d[j] > g[t][j]) {d[j] = g[t][j];}}}cout << res << endl;return;
}int main() {cin >> n;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> g[i][j];}}prim();return 0;
}

题目2:1141局域网

C++代码如下,

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110, M = 210;
int p[N];
int n, m;struct Edge {int a, b, w;bool operator< (const Edge &W) const {return w < W.w;}
}edges[M];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {cin >> n >> m;int s = 0;for (int i = 0; i < m; ++i) {cin >> edges[i].a >> edges[i].b >> edges[i].w;s += edges[i].w;}for (int i = 1; i <= n; ++i) p[i] = i;sort(edges, edges + m);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++;}}cout << s - res << endl;return 0;
}

题目3:1142繁忙的都市

C++代码如下,

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 310, M = 8010;
int n, m;
int p[N];struct Edge {int a, b, w;bool operator< (const Edge &W) const {return w < W.w;}
}edges[M];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++i) p[i] = i;for (int i = 0; i < m; ++i) {cin >> edges[i].a >> edges[i].b >> edges[i].w;}sort(edges, edges + m);int res = 0;int 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;cnt += 1;res = w;}}cout << cnt << " " << res << endl;return 0;
}

题目4

相关文章:

acwing算法提高之图论--最小生成树的典型应用

目录 1 介绍2 训练 1 介绍 本专题用来记录使用prim算法或kruskal算法求解的题目。 2 训练 题目1&#xff1a;1140最短网络 C代码如下&#xff0c; #include <iostream> #include <cstring>using namespace std;const int N 110, INF 0x3f3f3f3f; int g[N][N…...

springcloud基本使用二(远程调用)

创建两个springboot maven子项目 子项目名称分别为order-server和user-server 配置user-server子项目: 所需依赖: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId> </dependenc…...

代码随想录刷题day42| 01背包理论基础分割等和子集

文章目录 day41学习内容一、 01背包之二维数组解法1.1、什么是01背包1.2、动态规划五部曲1.2.1、 确定dp数组&#xff08;dp table&#xff09;以及下标的含义1.2.2、确定递推公式1.2.3、 dp数组如何初始化1.2.4、确定遍历顺序1.2.5、计算并返回最终结果 二、 01背包之一维数组…...

Python文件操作命令

文件操作 我知道你最近很累&#xff0c;是那种看不见的、身体上和精神上的疲惫感&#xff0c;但是请你一定要坚持下去。就算无人问津也好&#xff0c;技不如人也好&#xff0c;千万别让烦躁和焦虑毁了你的热情和定力。别贪心&#xff0c;我们不可能什么都有&#xff0c;也别灰心…...

CSS面试题---基础

1、css选择器及优先级 选择器优先级&#xff1a;内联样式>id选择器>类选择器、属性选择器、伪类选择器>标签选择器、微元素选择器 注意&#xff1a; !important优先级最高&#xff1b; 如果优先级相同&#xff0c;则最后出现的样式生效&#xff1b; 继承得到的样式优先…...

OpenHarmony实战开发-分布式数据管理

​介绍 本示例展示了在eTS中分布式数据管理的使用&#xff0c;包括KVManager对象实例的创建和KVStore数据流转的使用。 通过设备管理接口ohos.distributedDeviceManager &#xff0c;实现设备之间的kvStore对象的数据传输交互&#xff0c;该对象拥有以下能力详见 ;1、注册和解…...

微服务(基础篇-007-RabbitMQ部署指南)

目录 05-RabbitMQ快速入门--介绍和安装_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1LQ4y127n4?p65&vd_source60a35a11f813c6dff0b76089e5e138cc 1.单机部署 1.1.下载镜像 1.2.安装MQ 2.集群部署 2.1.集群分类 2.2.设置网络 视频地址&#xff1a; 05-Rab…...

C语言一维数组及二维数组详解

引言&#xff1a; 小伙伴们&#xff0c;我发现我正文更新的有些慢&#xff0c;但相信我&#xff0c;每一篇文章真的都很用心在写的&#xff0c;哈哈&#xff0c;在本篇博客当中我们将详细讲解一下C语言中的数组知识&#xff0c;方便大家后续的使用&#xff0c;有不会的也可以当…...

11.图像边缘检测的原理与实现

数字图像处理(19): 边缘检测算子(Roberts算子、Prewitt算子、Sobel算子 和 Laplacian算子) 数字图像处理(20): 边缘检测算子(Canny算子) 1.边缘检测介绍 1.1 边缘检测的基本原理 边缘是图像的基本特征&#xff0c;所谓的边缘就是指的图像的局部不连续性。灰度或者结构等信息的…...

RVM安装ruby笔记

环境 硬件&#xff1a;Macbook Pro 系统&#xff1a;macOS 14.1 安装公钥 通过gpg安装公钥失败&#xff0c;报错如下&#xff1a; 换了几个公钥地址&#xff08;hkp://subkeys.pgp.net&#xff0c;hkp://keys.gnupg.net&#xff0c;hkp://pgp.mit.edu&#xff09;&#xff0c;…...

电力系统负荷预测方法

电力系统负荷是什么&#xff1f; 所谓的电力负荷预测是指以电力负荷变化以及外界因素变化为基础&#xff0c;以特定的数学方法或者建立数学模型的方式为手段&#xff0c;通过对电力负荷历史数据进行分析&#xff0c;对电力系统的需求做出估计以及研究相关因素对电力负荷的影响…...

electron打包桌面版.exe之vue项目踩坑(vue3+electron 解决打包后首页打开空白,打包后路由不跳转及请求不到后端数据等问题)

vue项目https://www.qingplus.cn/components-web/index打包桌面版问题集合 一、静态资源加载问题 npm run electron_dev桌面版运行后页面空白&#xff0c;内容未加载。 填坑&#xff1a; 打包配置要用相对路径 vite.config.ts文件中的base要改成./&#xff0c;之前加了项目…...

MySQL学习笔记(持续更行ing)

级别&#xff1a; 1. 了解&#xff0c;面试概率10% 2. 掌握&#xff0c;面试概率50% 3. 重点&#xff0c;面试概率80% 目录 1. 数据库**** 1.1. 概念**** 1.2. 分类**** 1.2.1. 关系型数据库**** 1.2.1.1. SQL**** 1.2.2. 安装**** 1.2.2.1. Navicat**** 1.2.3. 非…...

服务器配置Huggingface并git clone模型和文件

服务器配置Huggingface并git clone模型和文件 参考&#xff1a;https://huggingface.co/welcome 1 注册hugging face 官网注册&#xff0c;并获取token【https://huggingface.co/settings/tokens】&#xff0c;用于登录 2 安装 2.1 安装lfs https://stackoverflow.com/qu…...

Rust 开发的高性能 HTTP 请求工具

一、简述 在现在的软件开发领域&#xff0c;HTTP请求的快速验证变得越来越重要。特别是对于后端开发人员和测试工程师来说&#xff0c;能够快速创建、执行并验证HTTP请求对于提升开发效率至关重要。近期有一个名为Hurl的开源项目&#xff0c;它被设计来高效执行HTTP请求&#…...

Android Studio 通过 WIFI 调试手机 app

操作流程 首先第一步&#xff0c;PC 和手机都需要连在同一个局域网 WIFI。 第二步&#xff0c;手机 USB 连上 PC&#xff0c;确保能查看到通过 USB 连上的设备&#xff1a; >>adb devices List of devices attached CSXasjdhwjqwjhqdh device (最好只看到一个连上的设置…...

RabbitMQ高级笔记

视频链接&#xff1a;【黑马程序员RabbitMQ入门到实战教程】 文章目录 1.发送者的可靠性1.1.生产者重试机制1.2.生产者确认机制1.3.实现生产者确认1.3.1.开启生产者确认1.3.2.定义ReturnCallback1.3.3.定义ConfirmCallback 2.MQ的可靠性2.1.数据持久化2.1.1.交换机持久化2.1.2.…...

【Qt】QtCreator交叉编译环境配置Qt mkspec

1、问题描述 在QtCreator中配置TI AM437x的交叉编译环境后,编译时报错,错误信息如下 error: gnu/stubs-soft.h: No such file or directory2、原因分析 1)环境变量CC 搜索网络,解决方法为修改交叉编译工具目录下环境配置脚本,即执行source时的文件。 本人环境为:linux…...

点点数据K参数加密逆向分析(RPC方案跟加密算法还原)

文章目录 1. 写在前面2. 接口分析3. 断点分析4. RPC调用5. 算法还原 【&#x1f3e0;作者主页】&#xff1a;吴秋霖 【&#x1f4bc;作者介绍】&#xff1a;擅长爬虫与JS加密逆向分析&#xff01;Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长…...

考研数学|《1800》+《660》精华搭配混合用(经验分享)

肯定不行&#xff0c;考研数学哪有这么容易的&#xff01; 先说说这两本习题册&#xff0c;李永乐老师推出的新版660题&#xff0c;相较于18年前的版本&#xff0c;难度略有降低&#xff0c;更加适合初学者。因此&#xff0c;对于处于基础阶段的学习者来说&#xff0c;新版660…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...