NO.96十六届蓝桥杯备战|图论基础-多源最短路|Floyd|Clear And Present Danger|灾后重建|无向图的最小环问题(C++)
多源最短路:即图中每对顶点间的最短路径
floyd算法本质是动态规划,⽤来求任意两个结点之间的最短路,也称插点法。通过不断在两点之间加⼊新的点,来更新最短路。
适⽤于任何图,不管有向⽆向,边权正负,但是最短路必须存在(也就是不存在负环)。
- 状态表⽰:
f[k][i][j]
表⽰:仅仅经过[1, k]
这些点,结点 i ⾛到结点 j 的最短路径的⻓度。 - 状态转移⽅程:
- 第⼀种情况,不选新来的点:
f[k][i][j] = f[k - 1][i][j]
; - 第⼆种情况,选择新来的点:
f[k][i][j] = f[k - 1][i][k] + f[k - 1][k][j]
- 空间优化:只会⽤到上⼀层的状态,因此可以优化到第⼀维。
- 初始化:
f[i][i] = 0
;f[i][j]
为初始状态下 i 到 j 的距离,如果没有边则为⽆穷。
- 填表顺序:
- ⼀定要先枚举 k ,再枚举 i 和 j 。因为我们填表的时候,需要依赖的是 k - 1 层的状态,因此 k 必须先枚举。
B3647 【模板】Floyd - 洛谷
#include <bits/stdc++.h>
using namespace std;const int N = 110;int n, m;
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i++) f[i][i] = 0;for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;f[a][b] = f[b][a] = min(f[a][b], c);}//floydfor (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++)cout << f[i][j] << " ";cout << endl;}return 0;
}
P2910 [USACO08OPEN] Clear And Present Danger S - 洛谷
#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 110, M = 1e4 + 10;int n, m;
int a[M];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++) cin >> a[i];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> f[i][j];for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);LL ret = 0;for (int i = 2; i <= m; i++){int x = a[i-1], y = a[i];ret += f[x][y];}cout << ret << endl;return 0;
}
P1119 灾后重建 - 洛谷
在floyd算法中,我们是⼀个点⼀个点加⼊到最短路的更新中,那么这道题其实就是限制了我们加点的时机。当从前往后遍历每次询问的时候,直到时间点在询问的时间t之前的点,都可以加⼊到最短路的更新中。
那么就可以⼀边读取询问,⼀边通过时间限制,更新最短路
#include <bits/stdc++.h>
using namespace std;const int N = 210, INF = 0x3f3f3f3f;int n, m;
int t[N];
int f[N][N];void floyd(int k)
{for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 0; i < n; i++) cin >> t[i];memset(f, 0x3f, sizeof f);for (int i = 0; i < n; i++) f[i][i] = 0;for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;f[a][b] = f[b][a] = min(f[a][b], c);}int Q; cin >> Q;int pos = 0;while (Q--){int a, b, c; cin >> a >> b >> c;while (pos < n && t[pos] <= c) floyd(pos++);if (t[a] > c || t[b] > c || f[a][b] == INF) cout << -1 << endl;else cout << f[a][b] << endl;}return 0;
}
P6175 无向图的最小环问题 - 洛谷
floyd算法的性质:
- 在计算第 k 层的时候,
f[i][j]
⾥⾯存储着中转点为[1, k - 1]
时的最短路。如果设环⾥的最⼤结点的编号为 k ,与k相邻的点为 i, j ,其中i < k && j < k && i != j
: - 那么我们在floyd算法循环到 k 的时候,这个环的最⼩⻓度为:
f[i][j] + e[i][k] + e[j][k]
。 - 环的最⼤编号是任意的,因此在所有情况下取最⼩值即可
#include <bits/stdc++.h>
using namespace std;const int N = 110, INF = 1e8;int n, m;
int e[N][N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;//memset(e, 0x3f, sizeof e);//memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)f[i][j] = e[i][j] = INF;for (int i = 1; i <= n; i++) e[i][i] = f[i][i] = 0;for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;e[a][b] = e[b][a] = f[a][b] = f[b][a] = min(e[a][b], c);}int ret = INF;for (int k = 1; k <= n; k++){//最小环for (int i = 1; i < k; i++)for (int j = i+1; j < k; j++)ret = min(ret, f[i][j] + e[i][k] + e[k][j]);//最短距离for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);}if (ret == INF) cout << "No solution." << endl;else cout << ret << endl;return 0;
}
相关文章:
NO.96十六届蓝桥杯备战|图论基础-多源最短路|Floyd|Clear And Present Danger|灾后重建|无向图的最小环问题(C++)
多源最短路:即图中每对顶点间的最短路径 floyd算法本质是动态规划,⽤来求任意两个结点之间的最短路,也称插点法。通过不断在两点之间加⼊新的点,来更新最短路。 适⽤于任何图,不管有向⽆向,边权正负&…...
OpenHarmony - 小型系统内核(LiteOS-A)(六)
OpenHarmony - 小型系统内核(LiteOS-A)(六) 七、文件系统 支持的文件系统 FAT 基本概念 FAT文件系统是File Allocation Table(文件配置表)的简称,主要包括DBR区、FAT区、DATA区三个区域。其…...
“星睿O6” AI PC开发套件评测 - Windows on Arm 安装指南和性能测评
引言 Radxa联合此芯科技和安谋科技推出全新的"星睿O6"迷你 ITX 主板。该系统搭载了 CIX P1(CD8180)12 核 Armv9 处理器,拥有高达30T算力的NPU和高性能的GPU,最高配备64GB LPDDR内存,并提供了如 5GbE、HDMI …...
JS实现RSA加密
目录 目标 环境 实现RSA加解密 计算RSA加密允许的最大字节长度 目标 使用JS实现RSA加密解密。计算RSA加密允许的最大字节长度。 环境 node-rsa 实现RSA加解密 const NodeRSA require(node-rsa);function getKey() {const keyLength512// 创建 RSA 密钥对const key new …...
Seata方案详细
Seata(Simple Extensible Autonomous Transaction Architecture)是阿里开源的分布式事务解决方案,支持多种事务模式,提供一站式的事务管理能力。以下是其核心原理、模式及实践的详细解析: 一、Seata核心架构与角色 Se…...
深入了解v-model的原理:v-model拆分为value属性和input事件,表单类组件的封装并用v-model简化代码
文章目录 1.v-model的原理1.1.验证:在input文本输入框中不使用v-model实现双向数据绑定1.2.验证:v-model在下拉菜单中的拆分 2.表单类组件的封装2.1.原理或步骤2.2.示例:表单类组件封装之下拉菜单select的封装 3.使用v-model简化代码完整代码 4.拓展示例:完成input文本输入框的…...
设计模式每日硬核训练 Day 14:组合模式(Composite Pattern)完整讲解与实战应用
🔄 回顾 Day 13:桥接模式小结 在 Day 13 中,我们学习了桥接模式(Bridge Pattern): 用于将“抽象”与“实现”分离,适用于双维度变化场景(如图形类型 渲染方式)。它强调…...
RMSIN论文阅读
自适应旋转卷积 (ARC)是否可以换成可变形卷积 研究背景 指向性遥感图像分割(RRSIS):旨在根据文本描述实现遥感图像中目标对象的像素级定位 像素级定位:像素级定位指的是在图像中对目标对象的每个像素进行准确的定位和标记。这意味…...
【音视频】FLV格式分析
FLV概述 FLV(Flash Video)是Adobe公司推出的⼀种流媒体格式,由于其封装后的⾳视频⽂件体积⼩、封装简单等特点,⾮常适合于互联⽹上使⽤。⽬前主流的视频⽹站基本都⽀持FLV。采⽤FLV格式封装的⽂件后缀为.flv。 FLV封装格式是由⼀个⽂件头(file header)和…...
华为OD机试真题——最小的调整次数/特异性双端队列(2025A卷:100分)Java/python/JavaScript/C++/C语言/GO六种最佳实现
2025 A卷 100分 题型 本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析; 并提供Java、python、JavaScript、C、C语言、GO六种语言的最佳实现方式! 2025华为OD真题目录全流程解析/备考攻略/经验分享 华为OD机试真题《最小的调…...
华为OD机试真题——统计匹配的二元组个数(2025A卷:100分)Java/python/JavaScript/C++/C语言/GO六种最佳实现
2025 A卷 100分 题型 本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析; 并提供Java、python、JavaScript、C、C语言、GO六种语言的最佳实现方式! 2025华为OD真题目录全流程解析/备考攻略/经验分享 华为OD机试真题《统计匹配…...
4.16学习总结
完成134. 加油站 - 力扣(LeetCode)算法题 学习了filewriter的相关方法,了解了字符流的底层原理...
java面试篇 4.9
目录 mybatis: 1、mybatis的执行流程 2、mybatis是否支持延迟加载? 当我们需要去开启全局的懒加载时: 3、mybatis的一级和二级缓存 微服务 1、springcloud五大组件有哪些 2、服务注册和发现是什么意思?springcloud如何实现…...
子函数嵌套的意义——以“颜色排序”为例(Python)
多一层缩进精减参数传递,参数少平铺书代码写更佳。 笔记模板由python脚本于2025-04-16 11:52:53创建,本篇笔记适合喜欢子函数嵌套结构代码形式的coder翻阅。 【学习的细节是欢悦的历程】 博客的核心价值:在于输出思考与经验,而不仅…...
Python深度学习实现验证码识别全攻略
放在前面 Python深度学习实现验证码识别全攻略 Python深度学习实现验证码识别全攻略 在网络安全领域,验证码作为人机区分的关键防线,广泛应用于登录、注册等场景。随着技术演进,验证码样式愈发复杂,传统识别手段力不从心&#…...
【Linux】su、su-、sudo、sudo -i、sudo su - 命令有什么区别?分别适用什么场景?
目录 su su- sudo sudo -i sudo su - /etc/sudoers su 该命令将启动非登录shell,即虽然以该用户身份启动shell,但使用的是原始用户的环境设置。普通用户账户运行 su 命令切换到另一用户账户,需提供要切换的账户的密码。root用户&…...
算法-同余原理
在计算n个数相加或者相乘再取余时,中间结果可能会溢出导致结果错误,这时可以使用同余原理 一、同余原理 ①加法同余 (a[1] a[2] ... a[n])% m > (a[1] % m a[2] % m ... a[n] % m) % m ② 乘法同余 (…...
深入理解卷积神经网络(CNN):从原理到实践
引言 卷积神经网络(Convolutional Neural Networks, CNN)是深度学习领域最具影响力的架构之一,尤其在计算机视觉任务中表现出色。自2012年AlexNet在ImageNet竞赛中一战成名以来,CNN不断演进,推动着图像识别、医疗影像分析、自动驾驶等领域的快…...
深度学习常见模块实现001
文章目录 1.学习目的2.常见模块使用与实现2.1 ResNet18实现2.2 SeNet模块2.3 CBAM模块 1.学习目的 深度学习在图像处理这块,很多模块已经成型,并没有很多新的东西,更多的是不同的模块堆叠,所以需要我们不断总结,动手实…...
Python实现贪吃蛇三
上篇文章Python实现贪吃蛇一,实现了一个贪吃蛇的基础版本。后面第二篇文章Python实现贪吃蛇二修改了一些不足,但最近发现还有两点需要优化: 1、生成食物的时候有概率和记分牌重合 2、游戏缺少暂停功能 先看生成食物的时候有概率和记分牌重合的…...
windows server C# IIS部署
1、添加IIS功能 windows server 2012、windows server 2016、windows server 2019 说明:自带的是.net 4.5 不需要安装.net 3.5 尽量使用 windows server 2019、2016高版本,低版本会出现需要打补丁的问题 2、打开IIS 3、打开iis应用池 .net 4.5 4、添…...
LLM小白自学笔记:1.两种指令微调
一、LoRA 简单来说,LoRA不直接调整个大模型的全部参数(那样太费资源),而是在模型的某些层(通常是注意力层)加个“旁路”——两个小的矩阵(低秩矩阵)。训练时只更新这俩小矩阵&#x…...
杰弗里·辛顿:深度学习教父
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 杰弗里辛顿:当坚持遇见突破,AI迎来新纪元 一、人物简介 杰弗…...
RHCE 第一次作业
一.定义延迟任务 1.安装邮件服务 [roothaiou ~]# yum install s-nail -y 2.配置邮件服务 [roothaiou ~]# vim /etc/mail.rc 3.测试邮件服务 [roothaiou ~]# echo 88888888 | mail -v -s Passion 13571532874163.com 4.设置定时任务 [roothaiou ~]# crontab -e 二.时间同步…...
库洛游戏一面+二面
目录 一面 1. ArrayList和LinkedList的区别,就是我在插入和删除的时候他们在时间复杂度上有什么区别 2. hashmap在java的底层是怎么实现的 3. 红黑树的实现原理 4. 红黑树的特点 5. 为什么红黑树比链表查询速度快 6. 在java中字符串的操作方式有几种 7. Stri…...
基于多模态深度学习的亚急性脊髓联合变性全流程预测与个性化管理技术方案
目录 技术方案文档1. 数据收集与预处理模块2. 多模态预测模型构建3. 术前风险评估系统4. 术中实时监测系统5. 术后并发症预测与护理6. 统计分析与验证模块7. 健康教育系统技术实现说明技术方案文档 1. 数据收集与预处理模块 功能:构建数据管道,清洗并整合多源数据 伪代码示…...
蓝桥杯日期的题型
做题思路 一般分为3个步骤,首先要定义一个结构体来存储月份的天数,第一循环日期,第二判断日期是否为闰年,第三就是题目求什么 结构体 static int[] ds{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 判断是否闰年的函数 public static void f(int m,int d){//被4整…...
【树形dp题解】dfs的巧妙应用
【树形dp题解】dfs的巧妙应用 [P2986 USACO10MAR] Great Cow Gathering G - 洛谷 题目大意: Bessie 正在计划一年一度的奶牛大集会,来自全国各地的奶牛将来参加这一次集会。当然,她会选择最方便的地点来举办这次集会。 每个奶牛居住在 N N …...
《AI大模型应知应会100篇》第20篇:大模型伦理准则与监管趋势
第20篇:大模型伦理准则与监管趋势 摘要 随着人工智能(AI)技术的飞速发展,尤其是大模型(如GPT、PaLM等)在自然语言处理、图像生成等领域的广泛应用,AI伦理问题和监管挑战日益凸显。本文将梳理当…...
线上教学平台(vue+springboot+ssm+mysql)含文档+PPT
线上教学平台(vuespringbootssmmysql)含文档PPT 该系统是一个在线教学平台,主要分为管理员和学员两个角色;管理员界面包含首页、交流中心、学员管理、资料类型管理、学习资料管理、交流论坛、我的收藏管理、留言板管理、考试管理…...
Being-0:具有视觉-语言模型和模块化技能的人形机器人智体
25年3月来自北大、北京智源和 BeingBeyond 的论文“Being-0: A Humanoid Robotic Agent with Vision-Language Models and Modular Skills”。 构建能够在现实世界具身任务中达到人类水平表现的自主机器人智体,是人形机器人研究的终极目标。近期,基于基…...
Fiddler 进行断点测试:调试网络请求
目录 一、什么是断点测试? 二、Fiddler 的断点功能 三、如何在 Fiddler 中设置断点? 步骤 1:启动 Fiddler 步骤 2:启用断点 步骤 3:捕获请求 步骤 4:修改请求或响应 四、案例:模拟登录失…...
决策树:ID3,C4.5,CART树总结
树模型总结 决策树部分重点关注分叉的指标,多叉还是单叉,处理离散还是连续值,剪枝方法,以及回归还是分类 一、决策树 ID3(Iterative Dichotomiser 3) 、C4.5、CART决策树 ID3:确定分类规则判别指标、寻找能够最快速降低信息熵的方…...
DDS信号发生器设计
一、基本概述 1.1 DDS简介 DDS信号发生器即直接数字频率合成(Direct Digital Frequency Synthesis,简称DDS)是一种利用数字技术生成信号的方法。它通过数字信号处理技术,将数字信号转换为模拟信号,从而生成高质量的正…...
23黑马产品经理Day01
今天过了一遍23黑马产品经理的基础视频 问题思考维度 抓住核心用户 为什么需要抓住核心用户? 主要原因:用户越来越细分,保持市场竞争力,产品开发推广更聚焦 做产品为什么要了解用户:了解用户的付费点,…...
18-21源码剖析——Mybatis整体架构设计、核心组件调用关系、源码环境搭建
学习视频资料来源:https://www.bilibili.com/video/BV1R14y1W7yS 文章目录 1. 架构设计2. 核心组件及调用关系3. 源码环境搭建3.1 测试类3.2 实体类3.3 核心配置文件3.4 映射配置文件3.5 遇到的问题 1. 架构设计 Mybatis整体架构分为4层: 接口层&#…...
东方潮流亮相广州益民艺术馆|朋克编码“艺术家潮玩”系列开幕引爆热潮
4月15日,由我的宇宙旗下公司朋克编码携“艺术家潮玩”系列亮相广州白云益民艺术馆,标志着其全国文化推广计划正式启航。本次展览围绕“潮玩艺术东方文化”展开,融合传统文化与当代潮流,以年轻化方式赋能中国文化出海。 展览现场潮…...
充电宝项目:规则引擎Drools学习
文章目录 规则引擎 Drools1 问题2 规则引擎概述2.1 规则引擎2.2 使用规则引擎的优势2.3 规则引擎应用场景2.4 Drools介绍 3 Drools入门案例3.1 创建springboot项目 引入依赖3.2 添加Drools配置类3.4 创建实体类Order3.5 orderScore.drl3.6 编写测试类 4 Drools基础语法4.1 规则…...
C++零基础实践教程 文件输入输出
模块八:文件输入输出 (数据持久化) 在之前的模块中,我们学习了如何使用程序处理数据。然而,当程序结束运行时,这些数据通常会丢失。数据持久化 (Data Persistence) 指的是将程序中的数据存储到非易失性存储介质(如硬盘…...
SpringAI+DeepSeek大模型应用开发——1 AI概述
AI领域常用词汇 LLM(LargeLanguage Model,大语言模型) 能理解和生成自然语言的巨型AI模型,通过海量文本训练。例子:GPT-4、Claude、DeepSeek、文心一言、通义干问。 G(Generative)生成式: 根据上…...
数据中台进化史:从概念萌芽到价值变现的蜕变之路
在数字化转型的浪潮中,数据中台已成为企业驾驭数据、驱动业务创新的关键力量。回顾数据中台的发展历程,犹如一场从混沌到有序、从萌芽到成熟的精彩蜕变,它由湖仓一体、数据治理平台、数据服务平台三大核心要素逐步构建而成,每一个…...
【Java学习笔记】运算符
运算符 运算符的类型 算数运算符 赋值运算符 关系运算符(比较哦啊运算符) 逻辑运算符 三元运算符 位运算符(需要二进制基础) 一、算数运算符 运算符计算范例结果正号77-负号b11; -b-11加法9918-减法10-82*乘法7*856/除法9…...
【python】OpenCV—Tracking(10.6)—People Counting
文章目录 1、功能描述2、代码实现3、效果展示4、完整代码5、涉及到的库函数6、参考来自 更多有趣的代码示例,可参考【Programming】 1、功能描述 借助 opencv-python,用 SSD 人形检测模型和质心跟踪方法实现对人群的计数 基于质心的跟踪可以参考 【pyt…...
JavaSE学习(前端初体验)
文章目录 前言一、准备环境二、创建站点(创建一个文件夹)三、将站点部署到编写器中四、VScode实用小设置五、案例展示 前言 首先了解前端三件套:HTML、CSS、JS HTML:超文本标记语言、框架层、描述数据的; CSS…...
智慧城市像一张无形大网,如何紧密连接你我他?
智慧城市作为复杂巨系统,其核心在于通过技术创新构建无缝连接的网络,使物理空间与数字空间深度融合。这张"无形大网"由物联网感知层、城市数据中台、人工智能中枢、数字服务入口和安全信任机制五大支柱编织而成,正在重塑城市运行规…...
Linux常用命令
一、history 用于显示历史命令。 history 10显示最近10条历史命令。!200使用第200行的指令。history -c清空历史记录。 二、pwd 用于显示当前绝对路径。 pwd显示当前绝对路径。 三、ls 用于以行的形式显示当前文件夹下所有内容。 ls -a显示所有内容,包括隐藏文…...
【AI】SpringAI 第二弹:接入 DeepSeek 官方服务
一、接入 DeepSeek 官方服务 通过一个简单的案例演示接入 DeepSeek 实现简单的问答功能 1.添加依赖 <dependency><groupId>org.springframework.ai</groupId><artifactId>spring-ai-starter-model-openai</artifactId> </dependency> 2…...
QT的信号槽的直接触发,队列触发,自动触发
在Qt中,信号槽机制是一个非常强大的特性,它用于实现对象之间的通信。除了默认的直接触发方式之外,Qt还提供了队列触发等不同的触发方式。 1. 直接触发(Direct Connection) 直接触发是最常见的连接方式,信…...
typescript html input无法输入解决办法
input里加上这个: onkeydown:(e: KeyboardEvent) > {e.stopPropagation();...
工厂能耗系统智能化解决方案 —— 安科瑞企业能源管控平台
安科瑞顾强 政策背景与“双碳”战略驱动 2025年《政府工作报告》明确提出“单位国内生产总值能耗降低3%左右”的目标,要求通过产业结构升级(如高耗能行业技术革新或转型)、能源结构优化(提高非化石能源占比)及数字化…...