程序员经验分享-hwhale

2023华为OD机试真题【计算快递业务主站点/回溯法/深度优先搜索】

2023-11-09

题目描述

快递覆盖的范围有N的站，如果A和B都可以用来中转，我们就称A-B站可达。如果A-B可达，B-C可达，则A-C达。我们现在有N个编号，如果s[i][j] =1，表示i-j可达，如果s[i][j] =0，表示i-j不可达。现用二维数组给定N个站点的可达关系，请计算至少选择从几个主站点出发，才能可达所有站点(覆盖所有站点业)
说明: s[i][j] 与s [j][i] 取值相同
输入描述:
第一行输入为N，N表示站点个数之后N行表示站点之间的可达关系，第i行第i个数值表示编号为i和之间是否可达输出描述:
输出站点个数，表示至少需要多少个主站点
补充说明:
1<N<10000
示例1
输入:
4
1 1 1 1
1 1 1 0
1 1 1 0
1 0 0 1
输出:
1
说明:
选择0号站点作为主站点，0站点可达其他所有站点，所以至少选择1个站点作为主站才能覆盖所有站点业务。

解题思路

siteCount表示站点数量，关系矩阵connectivityMatrix表示站点之间的可达性关系。coveredSites表示已覆盖站点。遍历所有站点，对于尚未覆盖的站点：
用tempSet存储当前站点能覆盖的站点。然后深度优先遍历找到所有可达站点，并存到tempSet中。然后将te

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

2023华为OD机试真题【计算快递业务主站点/回溯法/深度优先搜索】 的相关文章

  • 如何将 Pandas Dataframe 中的字符串转换为字符列表或数组？

    我有一个名为的数据框data 其中一列包含字符串 我想从字符串中提取字符 因为我的目标是对它们进行一次性编码并使之可用于分类 包含字符串的列存储在预测因子如下 predictors pd DataFrame data columns Seq

  • 将数组从 .npy 文件读入 Fortran 90

    我使用 Python 以二维数组 例如 X 的形式生成一些初始数据 然后使用 Fortran 对它们进行一些计算 最初 当数组大小约为 10 000 x 10 000 时 np savetxt 在速度方面表现良好 但是一旦我开始增加数组的维

  • R 编程中的字符串分割

    目前 下面的脚本将组合的项目代码拆分为特定的项目代码 rule2 lt c MR df 1 lt test grep paste rule2 sep collapse test Name y SpaceName 1 lt function

  • 从 git 签出后 nuget dll 丢失

    I have a C solution containing different projects On those projects I have some normal nuget packages like Newtonsoft Js

  • 如何获取本地文件系统上 docker 容器生成的内容（最小失败示例）

    这个问题是另一个问题的最小失败版本 如何获取本地文件系统上docker容器生成的内容 https stackoverflow com questions 34924011 how to get contents generated by a

  • 从 Android 中的过渡动画中排除 BottomNavigation

    我一直在四处寻找 但找不到有助于解决这个特定问题的答案 我的应用程序有一个自定义滑入 滑出效果 如下所示 Intent intent new Intent getApplicationContext MyActivity class sta

  • GKE 出现错误：ImagePullBackOff 和错误：ErrImagePull 错误

    当 kubectl 应用 yaml 将自定义构建的 docker 映像部署到 GCP 中的集群 编辑掉敏感信息 时 我收到以下错误 已尝试以下但没有运气 手动部署镜像 检查以确保防火墙规则允许 443 并且没有任何东西阻止它 尝试将容器注册

  • linux下无法安装Cairo包

    我在本地下载该软件包并尝试安装它 但出现此错误 R CMD INSTALL l usr local lib64 R library Cairo 1 5 1 tar gz 我得到他的错误 checking for PNG support in

  • 在地图上使用 find

    如何使用 find 和 aconst iterator如果你有一个地图定义为 typedef std pair

  • shell脚本“x$VARIABLE”中x的用途[重复]

    这个问题在这里已经有答案了 我正在查看一些 shell 脚本 comarison shcu 中 x 的用途是什么 if x USER x RUN AS USER then su RUN AS USER c CATALINA HOME bin

  • 如何使用 Spring AOP 建议静态方法？

    在执行类的静态方法之前和之后需要完成一些日志记录 我尝试使用 Spring AOP 来实现这一点 但它不起作用 而对于正常方法来说它起作用 请帮助我理解如何实现这一点 如果可以使用注释来完成 那就太好了 也许您应该在使用 Spring AO

  • 如何抑制 Pandas Future 警告？

    当我运行该程序时 Pandas 每次都会给出如下所示的 未来警告 D Python lib site packages pandas core frame py 3581 FutureWarning rename with inplace

  • 如果列表在初始化之前为空，则 jQuery 可排序无法与水平列表正常工作

    如果我在初始化后将元素添加到列表中 sortable它无法正常工作 参见示例jsFiddle http jsfiddle net NQMPr 1 示例 HTML div class container div br

  • 将 Zurb Foundation v5 升级到 v6.2 所需的工作

    将 Foundation 5 升级到 6 2 需要做什么工作以及需要做多少工作 我们的开发工作室正在接管现有 F5 项目的开发 看起来前端布局已经完成了 80 尽管我们可能会过渡到 JSX 但几乎没有什么会保持不变 我需要帮助来权衡 F6

  • 从最大到最小的3个整数

    我是 C 初学者 我使用 编程 使用 C 的原理与实践 第二版 问题如下 编写一个程序 提示用户输入三个整数值 然后以逗号分隔的数字顺序输出这些值 如果两个值相同 则应将它们排列在一起 include

  • 使用 lpSolve 优化 R 团队名单

    我是 R 新手 有一个想要解决的特定幻想运动队优化问题 我见过其他帖子使用 lpSolve 来解决类似的问题 但我似乎无法理解代码 下面的示例数据表 每个球员都在一个球队中 扮演着特定的角色 有薪水 并且每场比赛都有平均得分 我需要的限制是

  • C#“var”关键字在 VB.NET 中的等价物是什么？

    例如 我如何获得 VB NET静态类型局部变量是static赋值右侧的表达式的类型 像这样 Dim http msdn microsoft com en us library 7ee5a7s1 aspx我的变量 3 你还需要 选项推断 ht

  • 滑动时向 PageView 添加新页面

    我目前正在制作一个日历应用程序 我想向右或向左滑动以转到下个月或上个月 我使用 PageView 时首先设置了一个包含 3 个项目的数组 第一个页面是第二个项目 我想向右滑动并在末尾添加一个页面 我想向左滑动并在开头添加一个页面 目前 如果

  • 从 Flask 中的 S3 返回 PDF

    我正在尝试在 Flask 应用程序的浏览器中返回 PDF 我使用 AWS S3 来存储文件 并使用 boto3 作为与 S3 交互的 SDK 到目前为止我的代码是 s3 boto3 resource s3 aws access key id

  • Golang 优雅地关闭 HTTP 服务器并进行错误处理

    我正在让我的 HTTP 服务器正常关闭 我从帖子中获取了提示here https stackoverflow com questions 39320025 how to stop http listenandserve 并且到目前为止已经像

随机推荐

热门标签