[H最短路] lc2959. 关闭分部的可行集合数目(Floyd最短路+二进制枚举+模板题)
文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接:2959. 关闭分部的可行集合数目
2. 题目解析
看了看题好像还没啥思路,结果一看数据范围,好家伙…n 最大就 10 啊,那不直接闭眼直接 Floyd+枚举所有情况即可吗???
果然算法评级只有 6…只需要熟练掌握数据结构即可。

坑点:
- 最终要保持连通,需要特殊判断一下 在这里 WA 一次
- 无向图建双向边
- 时间复杂度: O ( 2 n ∗ n 3 ) O(2^n*n^3) O(2n∗n3)
- 空间复杂度: 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. 题目来源 链接:2959. 关闭分部的可行集合数目 2. 题目解析 看了看题好像还没啥思路,结果一看数据范围,好家伙…n 最大就 10 啊,那不直接闭眼直接 Floyd枚举所有情况即可吗?&…...
pyinstaller用法详解3
本文使用创作助手。 大家好,时隔多日,我又更新了pyinstaller的用法详解! 当然,这一次要比之前更详细,十分详细。 谢谢大家的支持,我们现在开始! 一、快速开始使用pyinstaller 我之前的文章…...
养猫新手不会挑智能猫砂盆?2024最新挑选干货分享!
不得不说智能猫砂盆真的帮了我很大的忙,四年以来我陆陆续续养了很多的猫咪,但是因为需要上班,所以有时候也对铲屎的工作有些力不从心,后面听了朋友的建议,去入手了智能猫砂盆,不得不说买智能猫砂盆也非常的…...
上海理工大学24计算机考研考情分析!初复试分值比55:45,复试逆袭人数不算多!
上海理工大学(University of Shanghai for Science and Technology),位于上海市,是一所以工学为主,工学、理学、经济学、管理学、文学、法学、艺术学等多学科协调发展的应用研究型大学;是上海市属重点建设大…...
Pandas库学习之DataFrame.drop()函数
Pandas库学习之DataFrame.drop()函数 一、简介 DataFrame.drop 是 Pandas 库中一个非常实用的函数,用于删除 DataFrame 中的行或列。通过指定列名或行索引,可以灵活地从数据集中移除不需要的数据。这对于数据清洗和预处理非常有用。 二、语法和参数 D…...
WHAT - 介绍一个不太一样的 UI 组件库 shadcn/ui
目录 一、介绍主要特点核心组件示例代码社区和支持总结 二、copy/paste1. 高度可定制性2. 避免依赖锁定3. 学习和理解4. 简化调试5. 项目需求变化 官方文档:https://ui.shadcn.com/docs 一、介绍 ShadCN (ShadCN/UI) 是一个现代的 React 组件库,旨在提…...
python--实验 11 模块
目录 知识点 模块基础 模块使用方式 自定义模块示例 模块的有条件执行 Python包结构 定义和导入包 常用第三方库及安装 实例代码 第三方库自动安装脚本 Python标准库介绍 PyInstaller 小结 实验 1.(基础题)制作文本进度条。 2.(基础题) 蒙特卡罗方法计算圆周率…...
Vue3+Vite+TS+Axios整合详细教程
1. Vite 简介 Vite是新一代的前端构建工具,在尤雨溪开发Vue3.0的时候诞生。类似于Webpack Webpack-dev-server。其主要利用浏览器ESM特性导入组织代码,在服务器端按需编译返回,完全跳过了打包这个概念,服务器随起随用。生产中利用…...
【深度学习入门篇 ⑨】循环神经网络实战
【🍊易编橙:一个帮助编程小伙伴少走弯路的终身成长社群🍊】 大家好,我是小森( ﹡ˆoˆ﹡ ) ! 易编橙终身成长社群创始团队嘉宾,橙似锦计划领衔成员、阿里云专家博主、腾讯云内容共创官…...
宝塔安装RabbitMq教程
需要放开15672端口,默认账号密码为guest/guest...
韦东山嵌入式linux系列-驱动进化之路:设备树的引入及简明教程
1 设备树的引入与作用 以 LED 驱动为例,如果你要更换LED所用的GPIO引脚,需要修改驱动程序源码、重新编译驱动、重新加载驱动。 在内核中,使用同一个芯片的板子,它们所用的外设资源不一样,比如A板用 GPIO A,…...
长轮询(Long Polling)实现原理和java代码示例
长轮询(Long Polling)背景 长轮询是一种在Web开发中常用的技术,用于实现服务器与客户端之间的即时通信或近乎实时的数据交换。在传统的轮询(Polling)中,客户端会定期向服务器发送请求以检查是否有新数据。…...
OWASP 移动应用 2024 十大安全风险
1. OWASP 移动应用 2024 十大安全风险 开放全球应用程序安全项目 (OWASP) 是一个非营利性基金会,致力于提高软件的安全性。自 2014、2016 年两次发布了移动应用的十大风险后,今年再次发布2024版。这对移动应用软件的检查工具有着…...
Qt界面假死原因
创建一个播放器类,继承QLabel,在播放器类中起一个线程用ffmpeg取流解码,将解码后的图像保存到队列,在gui线程中调用update()刷新显示。 当ffmpeg打开视频流失败后调用update()将qlabel刷新为黑色,有一定概率会使得qla…...
python调用MATLAB出错matlab.engine.MatlabExecutionError无法调用MATLAB函数报错
python调用MATLAB出错matlab.engine.MatlabExecutionError无法调用MATLAB函数报错 说明(废话)解决方案MATLAB异常乱码python矩阵转MATLAB矩阵matlab.engine.MatlabExecutionError 说明(废话) python调用MATLAB,调用m文件中的函数,刚开始都没有问题&…...
[GXYCTF2019]Ping Ping Ping1
打开靶机 结合题目名称,考虑是命令注入,试试ls 结果应该就在flag.php。尝试构造命令注入载荷。 cat flag.php 可以看到过滤了空格,用 $IFS$1替换空格 还过滤了flag,我们用字符拼接的方式看能否绕过,ag;cat$IFS$1fla$a.php。注意这里用分号间隔…...
成为git砖家(1): author 和 committer 的区别
大家好,我是白鱼。一直对 git author 和 committer 不太了解, 今天通过 cherry-pick 的例子搞清楚了区别。 原理 例如我克隆了著名开源项目 spdlog 的源码, 根据某个历史 commit A 创建了分支, 然后 cherry-pick 了这个 commit …...
Lianwei 安全周报|2024.07.15
新的一周又开始了,以下是本周「Lianwei周报」,我们总结推荐了本周的政策/标准/指南最新动态、热点资讯和安全事件,保证大家不错过本周的每一个重点! 政策/标准/指南最新动态 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 命令,方便在偶…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...
