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

难度：Hard

标签：位运算；图论；Floyd算法

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

题目中给出的n范围为1 <= n <= 10，那么说明最多的10个分部的情况下，可以选择关闭的可行情况有2^10种，这个数据量并不大，可以用暴力枚举做出来。

但是如何知道选择了哪些顶点呢？这里有用到位运算这个很巧妙的方法，一个int型数据有32位，我们最多只要用其中的10位即可表示所有的情况，同时还能用每一位来表示是否选择了某一个顶点（分部）。

利用Floyd算法可以求解出一个图中任意两个顶点之间的最小距离。当我们选择一个可能的集合时，判断这个集合中有的分部之间的最短距离是否会大于题目要求的最远距离maxDistance，如果有大于的，说明有分部之间最短的距离都无法满足要求。

需要注意的是，每一种情况我们只需要处理在集合中包含的分部。

class Solution {
public:
    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
        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) {
            int x = r[0], y = r[1], w = r[2];
            g[x][y] = min(g[x][y], w);
            g[y][x] = min(g[y][x], w);
        }
        vector<vector<int>> f(n); // 用f来存储每一种情况对应的图
        auto check = [&](int set) {
            for (int i = 0; i < n; i++) {
	            // 只要每种情况对应集合中的分部构成的图
                if ((set >> i) & 1) {
                    f[i] = g[i];
                }
            }

			// Floyd算法，处理f中分部之间的最短距离，需要根据set的值来选择进行计算
			// 因为在之前我们只选择了集合中有的分部建图
            for (int k = 0; k < n; k++) {
                if (((set >> k) & 1) == 0) continue;
                for (int i = 0; i < n; i++) {
                    if (((set >> i) & 1) == 0) continue;
                    for (int j = 0; j < n; j++) {
                        if (((set >> j) & 1) == 0) continue;
                        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                    }
                }
            }

			// 检查图中各个分部的最短距离
            for (int i = 0; i < n; i++) {
                if (((set >> i) & 1) == 0) continue;
                for (int j = 0; j < n; j++) {
                    if (((set >> j) & 1) && f[i][j] > maxDistance) {
                        return false;
                    }
                }
            }
            return true;
        };
        
        int res = 0;
        // 暴力枚举所有情况
        for (int i = 0; i < (1 << n); i++) {
            res += check(i); // true和false分别隐式转换为1和0
        }
        return res;
    }
};