千问 LeetCode 2959. 关闭分部的可行集合数目 Python3实现

这是一道经典的图论与状态压缩结合的题目。由于题目中明确给出分部的数量 n 最多为 10我们可以采用二进制枚举状态压缩来遍历所有可能的关闭方案并结合 Floyd-Warshall 算法来验证每种方案下剩余分部之间的最远距离是否满足条件。核心思路1. 二进制枚举使用一个从 0 到 2^n - 1 的整数 mask 来表示分部的保留状态。如果 mask 的第 i 位为 1表示保留第 i 个分部为 0 则表示关闭该分部。2. 初始化距离矩阵对于每一种枚举状态初始化一个 n x n 的距离矩阵。自身到自身的距离为 0其余初始化为无穷大。遍历给定的 roads如果道路两端的分部在当前状态下都被保留则更新它们之间的最短直接距离注意处理重边取最小值。3. Floyd 算法求最短路在保留的分部之间运行 Floyd 算法计算所有保留分部两两之间的最短距离。在松弛操作时需要确保中转点也是被保留的。4. 合法性判断遍历距离矩阵检查所有保留分部之间的最远距离是否都不超过 maxDistance。如果满足则当前方案可行结果计数加 1。Python3 代码实现class Solution:def numberOfSets(self, n: int, maxDistance: int, roads: list[list[int]]) - int:INF float(inf)ans 0# 1. 二进制枚举所有可能的关闭方案 (0 到 2^n - 1)for mask in range(1 n):# 2. 初始化距离矩阵dist [[INF] * n for _ in range(n)]for i in range(n):dist[i][i] 0# 3. 根据当前状态 mask 构建图for u, v, w in roads:# 只有当 u 和 v 对应的分部在当前方案中都被保留时才加入这条边if (mask u) 1 and (mask v) 1:# 两个分部之间可能有多条道路取最短的一条dist[u][v] min(dist[u][v], w)dist[v][u] min(dist[v][u], w)# 4. 运行 Floyd-Warshall 算法计算多源最短路径for k in range(n):# 如果中转点 k 被关闭则跳过if not (mask k) 1:continuefor i in range(n):if not (mask i) 1:continuefor j in range(n):if not (mask j) 1:continueif dist[i][k] dist[k][j] dist[i][j]:dist[i][j] dist[i][k] dist[k][j]# 5. 检查当前方案是否合法valid Truefor i in range(n):if not (mask i) 1:continuefor j in range(n):if not (mask j) 1:continueif dist[i][j] maxDistance:valid Falsebreakif not valid:breakif valid:ans 1return ans复杂度分析* 时间复杂度O(2^n times n^3)。共有 2^n 种状态对于每种状态Floyd 算法的时间复杂度为 O(n^3)。由于 n le 10总计算量在百万级别完全可以轻松通过。* 空间复杂度O(n^2)。主要用于存储距离矩阵。