LeetCode 题解工作台
关闭分部的可行集合数目
一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。 公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（ 也可能不关闭任何分部 ），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。 两个分部之间的 …
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 堆
答案摘要
我们注意到 $n \leq 10$，所以我们不妨考虑使用二进制枚举的方法来枚举所有的分部集合。 对于每个分部集合，我们可以使用 Floyd 算法来计算出剩余分部之间的最短距离，然后判断是否满足题目要求即可。具体地，我们先枚举中间点 ，再枚举起点 和终点 ，如果 $g[i][k] + g[k][j] \lt g[i][j]$，那么我们就用更短的距离 $g[i][k] + g[k][j]$ 更新 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。
公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。
两个分部之间的 距离 是通过道路长度之和的 最小值 。
给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi 长度为 wi的 无向 道路。
请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。
注意，关闭一个分部后，与之相连的所有道路不可通行。
注意，两个分部之间可能会有多条道路。
示例 1：
输入：n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]] 输出：5 解释：可行的关闭分部方案有： - 关闭分部集合 [2] ，剩余分部为 [0,1] ，它们之间的距离为 2 。 - 关闭分部集合 [0,1] ，剩余分部为 [2] 。 - 关闭分部集合 [1,2] ，剩余分部为 [0] 。 - 关闭分部集合 [0,2] ，剩余分部为 [1] 。 - 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。 总共有 5 种可行的关闭方案。
示例 2：
输入：n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]] 输出：7 解释：可行的关闭分部方案有： - 关闭分部集合 [] ，剩余分部为 [0,1,2] ，它们之间的最远距离为 4 。 - 关闭分部集合 [0] ，剩余分部为 [1,2] ，它们之间的距离为 2 。 - 关闭分部集合 [1] ，剩余分部为 [0,2] ，它们之间的距离为 2 。 - 关闭分部集合 [0,1] ，剩余分部为 [2] 。 - 关闭分部集合 [1,2] ，剩余分部为 [0] 。 - 关闭分部集合 [0,2] ，剩余分部为 [1] 。 - 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。 总共有 7 种可行的关闭方案。
示例 3：
输入：n = 1, maxDistance = 10, roads = [] 输出：2 解释：可行的关闭分部方案有： - 关闭分部集合 [] ，剩余分部为 [0] 。 - 关闭分部集合 [0] ，关闭后没有剩余分部。 总共有 2 种可行的关闭方案。
提示：
1 <= n <= 101 <= maxDistance <= 1050 <= roads.length <= 1000roads[i].length == 30 <= ui, vi <= n - 1ui != vi1 <= wi <= 1000- 一开始所有分部之间通过道路互相可以到达。
解题思路
方法一：二进制枚举 + Floyd 算法
我们注意到 ，所以我们不妨考虑使用二进制枚举的方法来枚举所有的分部集合。
对于每个分部集合，我们可以使用 Floyd 算法来计算出剩余分部之间的最短距离，然后判断是否满足题目要求即可。具体地，我们先枚举中间点 ，再枚举起点 和终点 ，如果 ，那么我们就用更短的距离 更新 。
时间复杂度 ，空间复杂度 。其中 和 分别是分部数量和道路数量。
class Solution:
def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
ans = 0
for mask in range(1 << n):
g = [[inf] * n for _ in range(n)]
for u, v, w in roads:
if mask >> u & 1 and mask >> v & 1:
g[u][v] = min(g[u][v], w)
g[v][u] = min(g[v][u], w)
for k in range(n):
if mask >> k & 1:
g[k][k] = 0
for i in range(n):
for j in range(n):
# g[i][j] = min(g[i][j], g[i][k] + g[k][j])
if g[i][k] + g[k][j] < g[i][j]:
g[i][j] = g[i][k] + g[k][j]
if all(
g[i][j] <= maxDistance
for i in range(n)
for j in range(n)
if mask >> i & 1 and mask >> j & 1
):
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(2^n * n^3) if using Floyd-Warshall for each subset, since there are 2^n subsets and n^3 operations per distance check. Space complexity is O(n^2) to store the graph distances. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect the candidate to recognize bitmask enumeration for all subsets of branches.
- question_mark
Look for correct use of shortest path algorithms to validate distances in remaining branches.
- question_mark
Check that candidate avoids redundant computations across similar subsets to optimize performance.
常见陷阱
外企场景- error
Failing to handle subsets with zero active branches correctly.
- error
Misapplying shortest path logic and missing the maxDistance constraint.
- error
Inefficient recomputation of distances for each subset without caching or memoization.
进阶变体
外企场景- arrow_right_alt
Limit closure to at most k branches and count valid sets.
- arrow_right_alt
Change maxDistance dynamically based on branch weights or priority.
- arrow_right_alt
Add weighted penalties for closing certain branches and count only optimal sets.