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

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

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

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

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...