当前位置: 首页 > 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 命令,方便在偶…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

深度学习习题2

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

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...