🔗 🔴 2959. Number of Possible Sets of Closing Branches 2077

tags: Biweekly Contest 119 圖(Graph) 枚舉(Enumeration) 位運算(Bit Manipulation) 最短路徑(Shortest Path) 狀態壓縮 Floyd-Warshall

題意

給定一個 連通 的 無向多重圖(Undirected Multigraph) ，其中有 nn 個點，另給定一個二維陣列 roadsroads ，其中 roads[i]=[ui,vi,wi]roads[i] = [u_i, v_i, w_i] 表示從 uiu_i 到 viv_i 有一條權重為 wiw_i 的無向邊。

現在，你需要刪除一些點和與其相鄰的所有邊，使得剩下的點之間任意點的最長距離不超過 maxDistancemaxDistance ，求有多少種刪除點的方案。

注意，兩個分部之間可能會有多條道路。

約束條件

  • 1≤n≤101 \leq n \leq 10
  • 1≤maxDistance≤1051 \leq maxDistance \leq 10^5
  • 0≤roads.length≤10000 \leq roads.length \leq 1000
  • roads[i].length=3roads[i].length = 3
  • 0≤ui,vi≤n−10 \leq u_i, v_i \leq n - 1
  • ui≠viu_i \neq v_i
  • 1≤wi≤10001 \leq w_i \leq 1000
  • 一開始時，所有點都是連通的。

思路：狀態壓縮 + Floyd-Warshall

由於點的數量 n≤10n \leq 10 ，而每個點只有保留或刪除兩種狀態，所以可以使用 狀態壓縮 的方法來枚舉所有可能的狀態，然後使用 Floyd-Warshall 演算法來計算該狀態下任意兩點之間的最短距離，再檢查是否有任意兩點之間的距離超過 maxDistancemaxDistance 。

具體步驟如下：

  1. 首先，我們需要建立一個 鄰接矩陣(Adjacent Matrix) gg 來表示給定的無向多重圖。對於任意兩個節點 uu 和 vv，g[u][v]g[u][v] 表示從 uu 到 vv 的最短距離。初始時，將所有距離設置為無限大，然後遍歷 roadsroads 數組，更新對應的距離。
  2. 接下來使用 狀態壓縮 的方法來枚舉所有保留的點的狀態。對於每個狀態 maskmask，創建一個子圖 g2g2，其中包含所有被選中的點(即 maskmask 中二進位為 1 的點)。
  3. 對於子圖 g2g2，使用 Floyd-Warshall 演算法來更新任意兩個被選中點之間的最短距離。
  4. 最後檢查在當前子圖中，任意兩個點之間的最短距離是否都不超過 maxDistancemaxDistance。如果滿足條件，則將方案數 ansans 加 11 。

複雜度分析

  • 時間複雜度：O(2n⋅n3)O(2^n \cdot n^3)，其中 nn 是點的數量。
    • 狀態壓縮的部分需要枚舉所有 2n2^n 種狀態。
    • 每個狀態下使用 Floyd-Warshall 演算法計算最短路徑的時間複雜度為 O(n3)O(n^3)。
  • 空間複雜度：O(n2)O(n^2)，需要一個二維陣列來表示圖。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
        # Build graph
        g = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            g[i][i] = 0
        for u, v, w in roads:
            g[u][v] = min(g[u][v], w)
            g[v][u] = min(g[v][u], w)
        
        ans = 0
        for mask in range(1 << n): # 狀態壓縮
            g2 = [[] for _ in range(n)] # subgraph
            for i in range(n):
                if mask >> i & 1:
                    g2[i] = g[i][:] # copy
            # Floyd-Warshall
            for k in range(n):
                if mask >> k & 1 == 0: continue
                for i in range(n):
                    if mask >> i & 1 == 0: continue
                    for j in range(n):
                        if g2[i][k] + g2[k][j] < g2[i][j]:
                            g2[i][j] = g2[i][k] + g2[k][j]
            # Check
            flag = True
            for i in range(n):
                if mask >> i & 1 == 0: continue
                for j in range(n):
                    if mask >> j & 1 == 0: continue
                    if g2[i][j] > maxDistance:
                        flag = False
                        break
                if not flag:
                    break
            ans += flag
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
        // Build graph
        vector<vector<int>> g(n, vector<int>(n, INT_MAX / 2));
        for (int i = 0; i < n; i++) g[i][i] = 0;
        for (auto& r : roads) {
            g[r[0]][r[1]] = min(g[r[0]][r[1]], r[2]);
            g[r[1]][r[0]] = min(g[r[1]][r[0]], r[2]);
        }
        int ans = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            // Subgraph
            vector<vector<int>> g2(n);
            for (int i = 0; i < n; i++) {
                if (mask >> i & 1) g2[i] = g[i];
            }
            // Floyd Warshall
            for (int k = 0; k < n; k++) {
                if (!(mask >> k & 1)) continue;
                for (int i = 0; i < n; i++) {
                    if (!(mask >> i & 1)) continue;
                    for (int j = 0; j < n; j++) {
                        if (g2[i][k] + g2[k][j] < g2[i][j]) {
                            g2[i][j] = g2[i][k] + g2[k][j];
                        }
                    }
                }
            }
            // Check
            bool flag = true;
            for (int i = 0; i < n && flag; i++) {
                if (!(mask >> i & 1)) continue;
                for (int j = 0; j < n && flag; j++) {
                    if (!(mask >> j & 1)) continue;
                    if (g2[i][j] > maxDistance) flag = false;
                }
            }
            ans += flag;
        }
        return ans;
    }
};

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail,
1 girl, solo, long hair, black hair, blue eyes, skirt, shirt, school uniform, standing, white shirt, short sleeves, pleated skirt, outdoors, sky, serafuku, (pink serafuku, pink school uniform), day, sailor collar, blurry, arm up, neckerchief, long skirt, girl