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

[H最短路] lc2959. 关闭分部的可行集合数目(Floyd最短路+二进制枚举+模板题)

文章目录

    • 1. 题目来源
    • 2. 题目解析

1. 题目来源

链接:2959. 关闭分部的可行集合数目

2. 题目解析

看了看题好像还没啥思路,结果一看数据范围,好家伙…n 最大就 10 啊,那不直接闭眼直接 Floyd+枚举所有情况即可吗???

果然算法评级只有 6…只需要熟练掌握数据结构即可。
在这里插入图片描述
坑点

  • 最终要保持连通,需要特殊判断一下 在这里 WA 一次
  • 无向图建双向边

  • 时间复杂度 O ( 2 n ∗ n 3 ) O(2^n*n^3) O(2nn3)
  • 空间复杂度 O ( n 2 ) O(n^2) O(n2)

class Solution {
public:int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {int r = roads.size();// 2进制枚举int res = 0;vector<bool> del(n);for (int i = 0; i < 1 << n; i ++ ) {for (int j = 0; j < n; j ++ ) del[j] = false;for (int j = 0; j < n; j ++ ) if ((i >> j) & 1) del[j] = true;// floyd 建图int d[n][n]; memset(d, 0x3f, sizeof d);for (int j = 0; j < n; j ++ ) d[j][j] = 0;for (int j = 0; j < roads.size(); j ++ ) {int x = roads[j][0], y = roads[j][1], w = roads[j][2];if (del[x] || del[y]) continue;d[x][y] = min(d[x][y], w);d[y][x] = min(d[y][x], w);}// 最短路计算for (int j = 0; j < n; j ++ )for (int k = 0; k < n; k ++ )for (int m = 0; m < n; m ++ )d[k][m] = min(d[k][m], d[k][j] + d[j][m]);// 校验int check = 1;for (int j = 0; j < n; j ++ ) {for (int k = 0; k < n; k ++ ) {if (del[j] || del[k]) continue;if (d[j][k] == 0x3f3f3f3f || d[j][k] > maxDistance) check = 0;}}res += check;}return res;}
};

相关文章:

[H最短路] lc2959. 关闭分部的可行集合数目(Floyd最短路+二进制枚举+模板题)

文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接&#xff1a;2959. 关闭分部的可行集合数目 2. 题目解析 看了看题好像还没啥思路&#xff0c;结果一看数据范围&#xff0c;好家伙…n 最大就 10 啊&#xff0c;那不直接闭眼直接 Floyd枚举所有情况即可吗&#xff1f;&…...

pyinstaller用法详解3

本文使用创作助手。 大家好&#xff0c;时隔多日&#xff0c;我又更新了pyinstaller的用法详解&#xff01; 当然&#xff0c;这一次要比之前更详细&#xff0c;十分详细。 谢谢大家的支持&#xff0c;我们现在开始&#xff01; 一、快速开始使用pyinstaller 我之前的文章…...

养猫新手不会挑智能猫砂盆?2024最新挑选干货分享!

不得不说智能猫砂盆真的帮了我很大的忙&#xff0c;四年以来我陆陆续续养了很多的猫咪&#xff0c;但是因为需要上班&#xff0c;所以有时候也对铲屎的工作有些力不从心&#xff0c;后面听了朋友的建议&#xff0c;去入手了智能猫砂盆&#xff0c;不得不说买智能猫砂盆也非常的…...

上海理工大学24计算机考研考情分析!初复试分值比55:45,复试逆袭人数不算多!

上海理工大学&#xff08;University of Shanghai for Science and Technology&#xff09;&#xff0c;位于上海市&#xff0c;是一所以工学为主&#xff0c;工学、理学、经济学、管理学、文学、法学、艺术学等多学科协调发展的应用研究型大学&#xff1b;是上海市属重点建设大…...

Pandas库学习之DataFrame.drop()函数

Pandas库学习之DataFrame.drop()函数 一、简介 DataFrame.drop 是 Pandas 库中一个非常实用的函数&#xff0c;用于删除 DataFrame 中的行或列。通过指定列名或行索引&#xff0c;可以灵活地从数据集中移除不需要的数据。这对于数据清洗和预处理非常有用。 二、语法和参数 D…...

WHAT - 介绍一个不太一样的 UI 组件库 shadcn/ui

目录 一、介绍主要特点核心组件示例代码社区和支持总结 二、copy/paste1. 高度可定制性2. 避免依赖锁定3. 学习和理解4. 简化调试5. 项目需求变化 官方文档&#xff1a;https://ui.shadcn.com/docs 一、介绍 ShadCN (ShadCN/UI) 是一个现代的 React 组件库&#xff0c;旨在提…...

python--实验 11 模块

目录 知识点 模块基础 模块使用方式 自定义模块示例 模块的有条件执行 Python包结构 定义和导入包 常用第三方库及安装 实例代码 第三方库自动安装脚本 Python标准库介绍 PyInstaller 小结 实验 1.(基础题)制作文本进度条。 2.(基础题) 蒙特卡罗方法计算圆周率…...

Vue3+Vite+TS+Axios整合详细教程

1. Vite 简介 Vite是新一代的前端构建工具&#xff0c;在尤雨溪开发Vue3.0的时候诞生。类似于Webpack Webpack-dev-server。其主要利用浏览器ESM特性导入组织代码&#xff0c;在服务器端按需编译返回&#xff0c;完全跳过了打包这个概念&#xff0c;服务器随起随用。生产中利用…...

【深度学习入门篇 ⑨】循环神经网络实战

【&#x1f34a;易编橙&#xff1a;一个帮助编程小伙伴少走弯路的终身成长社群&#x1f34a;】 大家好&#xff0c;我是小森( &#xfe61;ˆoˆ&#xfe61; ) &#xff01; 易编橙终身成长社群创始团队嘉宾&#xff0c;橙似锦计划领衔成员、阿里云专家博主、腾讯云内容共创官…...

宝塔安装RabbitMq教程

需要放开15672端口&#xff0c;默认账号密码为guest/guest...

韦东山嵌入式linux系列-驱动进化之路:设备树的引入及简明教程

1 设备树的引入与作用 以 LED 驱动为例&#xff0c;如果你要更换LED所用的GPIO引脚&#xff0c;需要修改驱动程序源码、重新编译驱动、重新加载驱动。 在内核中&#xff0c;使用同一个芯片的板子&#xff0c;它们所用的外设资源不一样&#xff0c;比如A板用 GPIO A&#xff0c…...

长轮询(Long Polling)实现原理和java代码示例

长轮询&#xff08;Long Polling&#xff09;背景 长轮询是一种在Web开发中常用的技术&#xff0c;用于实现服务器与客户端之间的即时通信或近乎实时的数据交换。在传统的轮询&#xff08;Polling&#xff09;中&#xff0c;客户端会定期向服务器发送请求以检查是否有新数据。…...

OWASP 移动应用 2024 十大安全风险

1. OWASP 移动应用 2024 十大安全风险 开放全球应用程序安全项目 &#xff08;OWASP&#xff09; 是一个非营利性基金会&#xff0c;致力于提高软件的安全性。自 2014、2016 年两次发布了移动应用的十大风险后&#xff0c;今年再次发布2024版。这对移动应用软件的检查工具有着…...

Qt界面假死原因

创建一个播放器类&#xff0c;继承QLabel&#xff0c;在播放器类中起一个线程用ffmpeg取流解码&#xff0c;将解码后的图像保存到队列&#xff0c;在gui线程中调用update()刷新显示。 当ffmpeg打开视频流失败后调用update()将qlabel刷新为黑色&#xff0c;有一定概率会使得qla…...

python调用MATLAB出错matlab.engine.MatlabExecutionError无法调用MATLAB函数报错

python调用MATLAB出错matlab.engine.MatlabExecutionError无法调用MATLAB函数报错 说明(废话)解决方案MATLAB异常乱码python矩阵转MATLAB矩阵matlab.engine.MatlabExecutionError 说明(废话) python调用MATLAB&#xff0c;调用m文件中的函数&#xff0c;刚开始都没有问题&…...

[GXYCTF2019]Ping Ping Ping1

打开靶机 结合题目名称&#xff0c;考虑是命令注入&#xff0c;试试ls 结果应该就在flag.php。尝试构造命令注入载荷。 cat flag.php 可以看到过滤了空格,用 $IFS$1替换空格 还过滤了flag&#xff0c;我们用字符拼接的方式看能否绕过,ag;cat$IFS$1fla$a.php。注意这里用分号间隔…...

成为git砖家(1): author 和 committer 的区别

大家好&#xff0c;我是白鱼。一直对 git author 和 committer 不太了解&#xff0c; 今天通过 cherry-pick 的例子搞清楚了区别。 原理 例如我克隆了著名开源项目 spdlog 的源码&#xff0c; 根据某个历史 commit A 创建了分支&#xff0c; 然后 cherry-pick 了这个 commit …...

Lianwei 安全周报|2024.07.15

新的一周又开始了&#xff0c;以下是本周「Lianwei周报」&#xff0c;我们总结推荐了本周的政策/标准/指南最新动态、热点资讯和安全事件&#xff0c;保证大家不错过本周的每一个重点&#xff01; 政策/标准/指南最新动态 01 《人工智能全球治理上海宣言》发布 我们强调共同促…...

Linux - 基础开发工具(yum、vim、gcc、g++、make/Makefile、git、gdb)

目录 Linux软件包管理器 - yum Linux下安装软件的方式 认识yum 查找软件包 安装软件 如何实现本地机器和云服务器之间的文件互传 卸载软件 Linux编辑器 - vim vim的基本概念 vim下各模式的切换 vim命令模式各命令汇总 vim底行模式各命令汇总 vim的简单配置 Linux编译器 - gc…...

Git使用介绍教程

Git使用介绍教程 小白第一次写博客,内容写的可能不是很详细,仅供参考,大家一起努力 gitee网址:https://gitee.com 大部分的开发团队都以 Git 作为自己的版本控制工具,需要对 Git 的使用非常的熟悉。这篇文章中本人整理了自己在开发过程中经常使用到的 Git 命令,方便在偶…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...