Question

2959. 关闭分部的可行集合数目

English Version

题目描述

一个公司在全国有 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 <= 10
• 1 <= maxDistance <= 105
• 0 <= roads.length <= 1000
• roads[i].length == 3
• 0 <= ui, vi <= n - 1
• ui != vi
• 1 <= wi <= 1000
• 一开始所有分部之间通过道路互相可以到达。

解法

方法一：二进制枚举 + Floyd 算法

我们注意到 $n \leq 10$，所以我们不妨考虑使用二进制枚举的方法来枚举所有的分部集合。

对于每个分部集合，我们可以使用 Floyd 算法来计算出剩余分部之间的最短距离，然后判断是否满足题目要求即可。具体地，我们先枚举中间点 $k$，再枚举起点 $i$ 和终点 $j$，如果 $g[i][k] + g[k][j] \lt g[i][j]$，那么我们就用更短的距离 $g[i][k] + g[k][j]$ 更新 $g[i][j]$。

时间复杂度 $O(2^n \times (n^3 + m))$，空间复杂度 $O(n^2)$。其中 $n$ 和 $m$ 分别是分部数量和道路数量。

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

class Solution {
  public int numberOfSets(int n, int maxDistance, int[][] roads) {
    int ans = 0;
    for (int mask = 0; mask < 1 << n; ++mask) {
      int[][] g = new int[n][n];
      for (var e : g) {
        Arrays.fill(e, 1 << 29);
      }
      for (var e : roads) {
        int u = e[0], v = e[1], w = e[2];
        if ((mask >> u & 1) == 1 && (mask >> v & 1) == 1) {
          g[u][v] = Math.min(g[u][v], w);
          g[v][u] = Math.min(g[v][u], w);
        }
      }
      for (int k = 0; k < n; ++k) {
        if ((mask >> k & 1) == 1) {
          g[k][k] = 0;
          for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
              g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
            }
          }
        }
      }
      int ok = 1;
      for (int i = 0; i < n && ok == 1; ++i) {
        for (int j = 0; j < n && ok == 1; ++j) {
          if ((mask >> i & 1) == 1 && (mask >> j & 1) == 1) {
            if (g[i][j] > maxDistance) {
              ok = 0;
            }
          }
        }
      }
      ans += ok;
    }
    return ans;
  }
}

class Solution {
public:
  int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
    int ans = 0;
    for (int mask = 0; mask < 1 << n; ++mask) {
      int g[n][n];
      memset(g, 0x3f, sizeof(g));
      for (auto& e : roads) {
        int u = e[0], v = e[1], w = e[2];
        if ((mask >> u & 1) & (mask >> v & 1)) {
          g[u][v] = min(g[u][v], w);
          g[v][u] = min(g[v][u], w);
        }
      }
      for (int k = 0; k < n; ++k) {
        if (mask >> k & 1) {
          g[k][k] = 0;
          for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
              g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
          }
        }
      }
      int ok = 1;
      for (int i = 0; i < n && ok == 1; ++i) {
        for (int j = 0; j < n && ok == 1; ++j) {
          if ((mask >> i & 1) & (mask >> j & 1) && g[i][j] > maxDistance) {
            ok = 0;
          }
        }
      }
      ans += ok;
    }
    return ans;
  }
};

func numberOfSets(n int, maxDistance int, roads [][]int) (ans int) {
  for mask := 0; mask < 1<<n; mask++ {
    g := make([][]int, n)
    for i := range g {
      g[i] = make([]int, n)
      for j := range g[i] {
        g[i][j] = 1 << 29
      }
    }
    for _, e := range roads {
      u, v, w := e[0], e[1], e[2]
      if mask>>u&1 == 1 && mask>>v&1 == 1 {
        g[u][v] = min(g[u][v], w)
        g[v][u] = min(g[v][u], w)
      }
    }
    for k := 0; k < n; k++ {
      if mask>>k&1 == 1 {
        g[k][k] = 0
        for i := 0; i < n; i++ {
          for j := 0; j < n; j++ {
            g[i][j] = min(g[i][j], g[i][k]+g[k][j])
          }
        }
      }
    }
    ok := 1
    for i := 0; i < n && ok == 1; i++ {
      for j := 0; j < n && ok == 1; j++ {
        if mask>>i&1 == 1 && mask>>j&1 == 1 && g[i][j] > maxDistance {
          ok = 0
        }
      }
    }
    ans += ok
  }
  return
}

function numberOfSets(n: number, maxDistance: number, roads: number[][]): number {
  let ans = 0;
  for (let mask = 0; mask < 1 << n; ++mask) {
    const g: number[][] = Array.from({ length: n }, () => Array(n).fill(Infinity));
    for (const [u, v, w] of roads) {
      if ((mask >> u) & 1 && (mask >> v) & 1) {
        g[u][v] = Math.min(g[u][v], w);
        g[v][u] = Math.min(g[v][u], w);
      }
    }
    for (let k = 0; k < n; ++k) {
      if ((mask >> k) & 1) {
        g[k][k] = 0;
        for (let i = 0; i < n; ++i) {
          for (let j = 0; j < n; ++j) {
            g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
          }
        }
      }
    }
    let ok = 1;
    for (let i = 0; i < n && ok; ++i) {
      for (let j = 0; j < n && ok; ++j) {
        if ((mask >> i) & 1 && (mask >> j) & 1 && g[i][j] > maxDistance) {
          ok = 0;
        }
      }
    }
    ans += ok;
  }
  return ans;
}