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

【LetMeFly】2959.关闭分部的可行集合数目：二进制枚举+Floyd算法

力扣题目链接：https://leetcode.cn/problems/number-of-possible-sets-of-closing-branches/

一个公司在全国有 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算法

不难发现最多一共10个点，因此可以使用二进制枚举每个分公司是否被移除的情况，最多有$2^{10}=1024$种可能。

对于每种情况，对没被移除的公式应用一下Flody算法即可得到任意两点之间的最短距离，就能判断这种移法是否可行。

• 时间复杂度$O(2^n\times n^3)$
• 空间复杂度$O(n^2)$

AC代码

C++

class Solution {
private:
    vector<bool> remain;
    vector<vector<int>> graph, distances;

    // 计算remain状态下任意被保留的两点之间的最短距离 并将结果保存在distances中
    void floyd() {
        for (int k = 0; k < remain.size(); k++) {
            if (!remain[k]) {
                continue;
            }
            for (int i = 0; i < remain.size(); i++) {
                if (!remain[i]) {
                    continue;
                }
                for (int j = 0; j < remain.size(); j++) {
                    if (!remain[j]) {
                        continue;
                    }
                    distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j]);
                }
            }
        }
    }
public:
    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
        graph = vector<vector<int>>(n, vector<int>(n, 100001));
        remain.resize(n);
        for (vector<int>& road : roads) {
            graph[road[1]][road[0]] = graph[road[0]][road[1]] = min(graph[road[0]][road[1]], road[2]);
        }
        int ans = 0;
        for (int state = 0; state < (1 << n); state++) {
            for (int i = 0; i < n; i++) {
                remain[i] = state & (1 << i);
            }
            distances = graph;
            floyd();
            for (int i = 0; i < n; i++) {
                if (!remain[i]) {
                    continue;
                }
                for (int j = i + 1; j < n; j++) {
                    if (!remain[j]) {
                        continue;
                    }
                    if (distances[i][j] > maxDistance) {
                        goto loop;
                    }
                }
            }
            ans++;
            loop:;
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/140507896