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

第三章 图论 No.4最小生成树的简单应用

文章目录

      • 裸题:1140. 最短网络
      • 裸题:1141. 局域网
      • 裸题:1142. 繁忙的都市
      • 裸题:1143. 联络员
      • 有些麻烦的裸题:1144. 连接格点

存在边权为负的情况下,无法求最小生成树

image.png

裸题:1140. 最短网络

1140. 最短网络 - AcWing题库
image.png
套个prim的板子即可

#include <iostream>
#include <cstring>
using namespace std;const int N = 110, INF = 0x3f3f3f3f;
int g[N][N];
int dis[N]; bool st[N];
int n;int prim()
{memset(dis, 0x3f, sizeof(dis));int res = 0;for (int i = 0; i < n; ++ i ){int x = -1;for (int j = 1; j <= n; ++ j ) if (!st[j] && (x == -1 || dis[x] > dis[j])) x = j;st[x] = true;if (i && dis[x] == INF) return INF;if (i) res += dis[x];for (int y = 1; y <= n; ++ y )dis[y] = min(dis[y], g[x][y]);}return res;
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; ++ i )for (int j = 1; j <= n; ++ j )scanf("%d", &g[i][j]);printf("%d\n", prim());return 0;
}

裸题:1141. 局域网

1141. 局域网 - AcWing题库
image.png

裸题,稀疏图,套个kruskal的板子就行
需要注意的是:题目给定的图可能存在多个连通块,若使用prim算法,需要对每个连通块求最小生成树,但是使用kruskal能直接求出所有连通块的最小生成树

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 110, M = 210;
struct Edge
{int x, y, w;bool operator<(const Edge& e) const {return w < e.w;}
}edges[M];int p[N];
int n, m;int find(int x)
{if (x != p[x]) p[x] = find(p[x]);return p[x];
}int kruskal()
{sort(edges, edges + m);for (int i = 1; i <= n; ++ i ) p[i] = i;int cnt = 0, res = 0;for (int i = 0; i < m; ++ i ){auto t = edges[i];int x = edges[i].x, y = edges[i].y, w = edges[i].w;x = find(x), y = find(y);if (x != y){cnt ++ ;res += w;p[x] = y;}}return res;
}int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < m; ++ i )scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);int sum = 0;for (int i = 0; i < m; ++ i ) sum += edges[i].w;printf("%d\n", sum - kruskal());return 0;
}

裸题:1142. 繁忙的都市

1142. 繁忙的都市 - AcWing题库
依然是套kruskal的板子
image.png

#include <iostream>
#include <algorithm>
using namespace std;const int N = 310 ,M = 8010;
struct Edge
{int x, y, w;bool operator<(const Edge& e) const{return w < e.w;}
}edges[M];int n, m;
int p[N];int find(int x)
{if (x != p[x]) p[x] = find(p[x]);return p[x];
}int kruskal()
{sort(edges, edges + m);int res = 0;for (int i = 1; i <= n; ++ i ) p[i] = i;for (int i = 0; i < m; ++ i ){auto t = edges[i];int x = t.x, y = t.y, w = t.w;x = find(x), y = find(y);if (x != y){res = max(res, w);p[x] = y;}}return res;
}int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < m; ++ i )scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);printf("%d %d\n", n - 1, kruskal());return 0;
}

裸题:1143. 联络员

1143. 联络员 - AcWing题库
image.png

添加所有必选的边,维护并查集,然后再对非必选的边做kruskal


#include <iostream>
#include <algorithm>
using namespace std;const int N = 2010, M = 10010;
struct Edge
{int x, y, w;bool operator<(const Edge& e) const {return w < e.w;}
}edges[M];int n, m, cnt;
int p[N];int find(int x)
{if (x != p[x]) p[x] = find(p[x]);return p[x];
}int kruskal()
{int res = 0;for (int i = 0; i < cnt; ++ i ){auto t = edges[i];int x = t.x, y = t.y, w = t.w;x = find(x), y = find(y);if (x != y){res += w;p[x] = y;}}return res;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++ i ) p[i] = i;int t, x, y, d;int res = 0;while ( m -- ){scanf("%d%d%d%d", &t, &x, &y, &d);if (t == 1){x = find(x), y = find(y);if (x != y) p[x] = y;res += d;}else{edges[cnt].x = x, edges[cnt].y = y, edges[cnt].w = d;cnt ++ ;}}sort(edges, edges + cnt);res += kruskal();printf("%d\n", res);return 0;
}

有些麻烦的裸题:1144. 连接格点

1144. 连接格点 - AcWing题库
image.png

点阵为图中的点,将二维坐标转换成一维,作为点的编号
添加已有连线后,做kruskal即可

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010;
struct Edge
{int x, y, w;bool operator<(const Edge& e) const {return w < e.w;}
}edges[2 * N * N];int n, m, cnt = 1;
int p[N * N];
int g[N][N]; // 二维到一维
int dx[3] = { 0, 1, 0 }, dy[3] = { 0, 0, 1 };int find(int x)
{if (x != p[x]) p[x] = find(p[x]);return p[x];
}int kruskal()
{int res = 0;for (int i = 0; i < cnt; ++ i ){auto t = edges[i];int x = t.x, y = t.y, w = t.w;x = find(x), y = find(y);if (x != y){res += w;p[x] = y;}}return res;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++ i )for (int j = 1; j <= m; ++ j )g[i][j] = cnt ++ ;for (int i = 1; i < cnt; ++ i ) p[i] = i;int x1, x2, y1, y2;while (~scanf("%d%d%d%d", &x1, &y1, &x2, &y2)){int x = g[x1][y1], y = g[x2][y2];x = find(x), y = find(y);if (x != y) p[x] = y;}cnt = 0;for (int i = 1; i <= n; ++ i )for (int j = 1; j <= m; ++ j )for (int k = 1; k <= 2; ++ k ){int a = i + dx[k], b = j + dy[k];if (a >= 1 && a <= n && b >= 1 && b <= m){int x = g[i][j], y = g[a][b];edges[cnt ++ ] = { x, y, k };}}sort(edges, edges + cnt);printf("%d\n", kruskal());return 0;
}

debug:n * m的矩阵中,相邻两点之间存在一条边,那么矩阵中的边数应该为m(n-1) + n(m-1),大概就是2 * n * n,数组开小了导致SF
尽量不要在for循环中定义除了循环变量之外的变量

image.png
需要注意的是,200万条边进行排序会消耗很多时间,由于边的权值只有1和2,所以可以先添加权值为1的边,再添加权值为2的边

相关文章:

第三章 图论 No.4最小生成树的简单应用

文章目录 裸题&#xff1a;1140. 最短网络裸题&#xff1a;1141. 局域网裸题&#xff1a;1142. 繁忙的都市裸题&#xff1a;1143. 联络员有些麻烦的裸题&#xff1a;1144. 连接格点 存在边权为负的情况下&#xff0c;无法求最小生成树 裸题&#xff1a;1140. 最短网络 1140. 最…...

微服务-nacos配置管理

Nacos配置管理 统一配置管理&#xff1a;一次配置更改并支持热更新。将核心配置存储到配置管理服务&#xff0c;当微服务启动时会自动读取配置管理服务中的配置信息并结合本地配置启动。当配置改动时&#xff0c;配置管理服务会自动通知微服务&#xff0c;微服务读取新配置并自…...

【开发问题】flink的sql任务,用命令行执行

flink-sql 命令行flink-sql的客户端sql文件地址sql的内容 命令行 /mnt/flink/flink-1.17.1/bin/sql-client.sh embedded -f /mnt/flink/flink-1.17.1/examples/sql/oracle2Oracle flink-sql的客户端 /mnt/flink/flink-1.17.1/bin/sql-client.shsql文件地址 /mnt/flink/flink-1…...

Git常见问题

git clone 提示OpenSSL SSL_read git clone 时提示Connection was reset, errno 10054类错误 fatal: unable to acce ss https://github.com/fex-team/ueditor.git/: OpenSSL SSL_read: Connection was reset, errno 10054 备注&#xff1a;以下方法只是归纳整理&#xff0c;…...

Android如何实现开机自启

开机自启有很多种办法&#xff0c;下面用广播的方式实现。 1、首先先创建广播&#xff0c;开机代码 /*** Created by Forrest.* User: Administrator* Date: 2023/3/6* Description:*/ public class BootCompleteReceiver extends BroadcastReceiver {Overridepublic void on…...

Java数组实现的简单点名器

Java数组实现的简单点名器 需求分析代码实现小结Time 需求分析 Java数组实现的简单点名器 用数组将名单存储&#xff0c;然后调用Random函数取随机数实现随机点名。 代码实现 import java.util.Random;public class DianMingDemo {public static void main(String[] args) {//…...

百度UEditor编辑器如何关闭抓取远程图片功能

百度UEditor编辑器如何关闭抓取远程图片功能 这个坑娘的功能&#xff0c;开始时居然不知道如何触发&#xff0c;以为有个按钮&#xff0c;点击一下触发&#xff0c;翻阅了文档&#xff0c;没有发现&#xff0c;然后再网络上看到原来是复制粘贴非白名单内的图片到编辑框时触发&a…...

网站无法访问的常见原因

有多种问题可能会阻止用户访问您的网站。本文将解决无法访问网站&#xff0c;且没有错误消息指示确切问题的情况&#xff0c;希望对您有所帮助。 无法访问网站的常见原因有&#xff1a; (1)DNS 设置不正确。 (2)域名已过期。 (3)空白或没有索引文件。 (4)网络连接问题。 DNS 设…...

(树) 剑指 Offer 34. 二叉树中和为某一值的路径 ——【Leetcode每日一题】

❓ 剑指 Offer 34. 二叉树中和为某一值的路径 难度&#xff1a;中等 给你二叉树的根节点 root 和一个整数目标和 targetSum &#xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a…...

HDFS集群滚动升级以及回滚相关

HDFS集群滚动升级以及回滚相关 介绍不停机滚动升级非联邦HA集群联邦HA集群 停机升级--非HA集群HDFS集群降级和回滚异同点共同点不同点 HA集群降级&#xff08;downgrade&#xff09;注意事项 集群回滚操作 介绍 在hadoop v2中&#xff0c;HDFS支持namenode高可用&#xff08;H…...

【LeetCode】094. 分割回文串II

文章目录 1. 解题思路1.1 创建dp表1.2 状态转移方程1.3 提前求出所有子串是否是回文串 2. 整体代码 1. 解题思路 1.1 创建dp表 这道题我们使用动态规划的方法来解&#xff0c;首先创建一个大小为字符串长度的dp表。dp[i] 表示 s[0, i] 的字符串最小划分多少次可以全划分为回文…...

CBCGPRibbon 添加背景图片

resource.h中声明资源的ID&#xff1a;ID_RIBBON_BACKIMAGE rc文件中添加png图片路径&#xff1a; ID_RIBBON_BACKIMAGE PNG DISCARDABLE "res\\bkribbon.png" 代码中添加下测&#xff1a; //添加背景图片 m_wndRibbonBar.SetBackgroundImage(ID_RIB…...

无涯教程-Perl - last 语句函数

当在循环内遇到 last 语句时&#xff0c;循环立即终止&#xff0c;程序控制在循环后的下一条语句处恢复。您可以为LABEL提供最后一个语句&#xff0c;其中LABEL是循环的标签。 last 语句可以在嵌套循环内使用&#xff0c;如果未指定LABEL&#xff0c;则该语句将适用于最近的循环…...

网络安全 Day13-Linux三剑客awk知识

Linux三剑客awk知识 1. awk 介绍2. awk 语法3. 练习 1. awk 介绍 awk 是一门语言, 也是一个命令,Linux 有三剑客命令: grep/sed/awk三剑客的特长 grep 过滤内容sed 取行awk 取列 2. awk 语法 取列 取第一列文件($1): awk {print $1} 文件指定分隔符为文件: awk -F "指…...

java讲解Spring Boot配置文件级别 相互覆盖关系 解决一方不愿意给数据库密码 一方不愿意给源码时 数据库配置问题

前面 我们讲过Spring Boot 修改临时变量的方式 但另一个场景 就是 我们 在本地开发环境 用的是一个配置 但如果项目经理上线 他想改这些配置 怎么弄呢 特别是数据库之类的配置 很多线上是不太一样的 那么 我们先看一个比较基本的方法 在配置文件的同目录下创建一个目录 叫 con…...

点击表格行高亮

css中三元表达式 :class"[activeIndex index ? color : , item]"点击行高亮 <div click"actvied(index)" :class"[activeIndex index ? color : , item]"v-for"(item, index) in tableData" :key"index">{{ item…...

基于粒子群优化算法的配电网光伏储能双层优化配置模型[IEEE33节点](选址定容)(Matlab代码实现)

目录 &#x1f4a5;1 概述 &#x1f4da;2 运行结果 &#x1f389;3 参考文献 &#x1f308;4 Matlab代码、数据、讲解 &#x1f4a5;1 概述 由于能源的日益匮乏&#xff0c;电力需求的不断增长等&#xff0c;配电网中分布式能源渗透率不断提高&#xff0c;且逐渐向主动配电网方…...

零代码爬虫平台SpiderFlow的安装

什么是 Spider Flow &#xff1f; Spider Flow 是一个高度灵活可配置的爬虫平台&#xff0c;用户无需编写代码&#xff0c;以流程图的方式&#xff0c;即可实现爬虫。该工具支持多数据源、自动保存至数据库、任务监控、抓取 JS 动态渲染页面、插件扩展&#xff08;OCR 识别、邮…...

Java 与其他编程语言:比较分析

Java 擅长可移植性和可靠性&#xff0c;Python 擅长通用性和简单性&#xff0c;JavaScript 擅长 Web 开发&#xff0c;C 擅长性能&#xff0c;Go 擅长效率。 在广阔的软件开发世界中&#xff0c;选择正确的编程语言对于任何项目的成功都至关重要。Java 是一种以其多功能性和可移…...

Linux性能分析工具介绍(二)--内存、进程、磁盘、IO分析

目录 一、引言 二、Linux性能分析工具介绍 ------>2.1、进程 ------>2.2、内存 ------>2.3、磁盘 ------>2.4、IO 一、引言 本章从内存、IO、进程的角度,分析linux系统的性能 二、Linux性能分析工具介绍 2.1、进程 2.1.1、top top命令可以动态查看进程…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

【iOS】 Block再学习

iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...