Hard
题目描述
有一家公司在全国有 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
示例 3：
输入：n = 1, maxDistance = 10, roads = []
输出：2
约束：
1 <= n <= 101 <= maxDistance <= 10^50 <= roads.length <= 1000roads[i].length == 30 <= ui, vi <= n - 1ui != vi1 <= wi <= 1000- 所有分支机构都可以通过一些道路相互到达。
解题思路
这是一道典型的位运算枚举 + Floyd-Warshall 最短路径算法的问题。
核心思路：
- 状态枚举：由于 n ≤ 10，我们可以枚举所有可能的分支机构关闭状态。用位掩码表示，总共有 2^n 种状态。
- 图构建：对于每种状态，我们需要构建一个只包含未关闭分支机构的图。
- 最短路径：使用 Floyd-Warshall 算法计算剩余分支机构之间的最短距离。
- 距离验证：检查是否所有剩余分支机构之间的距离都不超过 maxDistance。
算法步骤：
- 遍历所有 2^n 种关闭状态（用位掩码表示）
- 对于每种状态：
- 如果没有剩余分支机构（全部关闭），则该状态有效
- 否则，构建包含剩余分支机构的邻接矩阵
- 使用 Floyd-Warshall 算法计算最短路径
- 检查任意两个剩余分支机构之间的距离是否 ≤ maxDistance
优化细节：
- 初始化距离矩阵时，将不可达的距离设为无穷大
- 对于同一对分支机构的多条道路，选择最短的那条
- Floyd-Warshall 的时间复杂度是 O(n³)，总体复杂度是 O(2^n × n³)
由于 n ≤ 10，这个复杂度是完全可接受的。
代码实现
class Solution {
public:
int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
int count = 0;
// 枚举所有可能的关闭状态
for (int mask = 0; mask < (1 << n); mask++) {
// 获取剩余的分支机构
vector<int> active;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) {
active.push_back(i);
}
}
// 如果没有剩余分支机构，该状态有效
if (active.empty()) {
count++;
continue;
}
// 如果只有一个分支机构，该状态有效
if (active.size() == 1) {
count++;
continue;
}
// 构建距离矩阵
vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
// 初始化对角线
for (int i = 0; i < n; i++) {
dist[i][i] = 0;
}
// 添加道路
for (auto& road : roads) {
int u = road[0], v = road[1], w = road[2];
if ((mask & (1 << u)) == 0 && (mask & (1 << v)) == 0) {
dist[u][v] = min(dist[u][v], w);
dist[v][u] = min(dist[v][u], w);
}
}
// Floyd-Warshall 算法
for (int k = 0; k < n; k++) {
if (mask & (1 << k)) continue;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) continue;
for (int j = 0; j < n; j++) {
if (mask & (1 << j)) continue;
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
// 检查所有剩余分支机构之间的距离
bool valid = true;
for (int i : active) {
for (int j : active) {
if (dist[i][j] > maxDistance) {
valid = false;
break;
}
}
if (!valid) break;
}
if (valid) {
count++;
}
}
return count;
}
};
class Solution:
def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
count = 0
# 枚举所有可能的关闭状态
for mask in range(1 << n):
# 获取剩余的分支机构
active = []
for i in range(n):
if (mask & (1 << i)) == 0:
active.append(i)
# 如果没有剩余分支机构或只有一个分支机构，该状态有效
if len(active) <= 1:
count += 1
continue
# 构建距离矩阵
dist = [[float('inf')] * n for _ in range(n)]
# 初始化对角线
for i in range(n):
dist[i][i] = 0
# 添加道路
for u, v, w in roads:
if (mask & (1 << u)) == 0 and (mask & (1 << v)) == 0:
dist[u][v] = min(dist[u][v], w)
dist[v][u] = min(dist[v][u], w)
# Floyd-Warshall 算法
for k in range(n):
if mask & (1 << k):
continue
for i in range(n):
if mask & (1 << i):
continue
for j in range(n):
if mask & (1 << j):
continue
if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 检查所有剩余分支机构之间的距离
valid = True
for i in active:
for j in active:
if dist[i][j] > maxDistance:
valid = False
break
if not valid:
break
if valid:
count += 1
return count
public class Solution {
public int NumberOfSets(int n, int maxDistance, int[][] roads) {
int count = 0;
// 枚举所有可能的关闭状态
for (int mask = 0; mask < (1 << n); mask++) {
// 获取剩余的分支机构
var active = new List<int>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) {
active.Add(i);
}
}
// 如果没有剩余分支机构或只有一个分支机构，该状态有效
if (active.Count <= 1) {
count++;
continue;
}
// 构建距离矩阵
int[,] dist = new int[n, n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i, j] = i == j ? 0 : int.MaxValue;
}
}
// 添加道路
foreach (var road in roads) {
int u = road[0], v = road[1], w = road[2];
if ((mask & (1 << u)) == 0 && (mask & (1 << v)) == 0) {
dist[u, v] = Math.Min(dist[u, v], w);
dist[v, u] = Math.Min(dist[v, u], w);
}
}
// Floyd-Warshall 算法
for (int k = 0; k < n; k++) {
if ((mask & (1 << k)) != 0) continue;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) continue;
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) continue;
if (dist[i, k] != int.MaxValue && dist[k, j] != int.MaxValue) {
dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
}
}
}
}
// 检查所有剩余分支机构之间的距离
bool valid = true;
foreach (int i in active) {
foreach (int j in active) {
if (dist[i, j] > maxDistance) {
valid = false;
break;
}
}
if (!valid) break;
}
if (valid) {
count++;
}
}
return count;
}
}
var numberOfSets = function(n, maxDistance, roads) {
let count = 0;
// Try all possible subsets of branches (2^n possibilities)
for (let mask = 0; mask < (1 << n); mask++) {
let activeBranches = [];
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
activeBranches.push(i);
}
}
// If 0 or 1 active branches, it's always valid
if (activeBranches.length <= 1) {
count++;
continue;
}
// Build adjacency matrix for active branches
let dist = Array(n).fill(null).map(() => Array(n).fill(Infinity));
// Initialize distances
for (let i = 0; i < n; i++) {
dist[i][i] = 0;
}
// Add roads between active branches
for (let [u, v, w] of roads) {
if ((mask & (1 << u)) && (mask & (1 << v))) {
dist[u][v] = Math.min(dist[u][v], w);
dist[v][u] = Math.min(dist[v][u], w);
}
}
// Floyd-Warshall algorithm
for (let k of activeBranches) {
for (let i of activeBranches) {
for (let j of activeBranches) {
if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
// Check if all active branches are within maxDistance
let valid = true;
for (let i of activeBranches) {
for (let j of activeBranches) {
if (dist[i][j] > maxDistance) {
valid = false;
break;
}
}
if (!valid) break;
}
if (valid) {
count++;
}
}
return count;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |