[H最短路] lc2959. 关闭分部的可行集合数目(Floyd最短路+二进制枚举+模板题)

1. 题目来源

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

2. 题目解析

看了看题好像还没啥思路，结果一看数据范围，好家伙…n 最大就 10 啊，那不直接闭眼直接 Floyd+枚举所有情况即可吗？？？

果然算法评级只有 6…只需要熟练掌握数据结构即可。

坑点：

• 最终要保持连通，需要特殊判断一下 在这里 WA 一次
• 无向图建双向边

---

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

---

class Solution {
public:
    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
        int r = roads.size();
        // 2进制枚举
        int res = 0;
        vector<bool> del(n);
        for (int i = 0; i < 1 << n; i ++ ) {
            for (int j = 0; j < n; j ++ ) del[j] = false;
            for (int j = 0; j < n; j ++ ) 
                if ((i >> j) & 1) 
                    del[j] = true;
            
            // floyd 建图
            int d[n][n]; memset(d, 0x3f, sizeof d);
            for (int j = 0; j < n; j ++ ) d[j][j] = 0;
            for (int j = 0; j < roads.size(); j ++ ) {
                int x = roads[j][0], y = roads[j][1], w = roads[j][2];
                if (del[x] || del[y]) continue;
                d[x][y] = min(d[x][y], w);
                d[y][x] = min(d[y][x], w);
            }

            // 最短路计算
            for (int j = 0; j < n; j ++ )
                for (int k = 0; k < n; k ++ )
                    for (int m = 0; m < n; m ++ )
                        d[k][m] = min(d[k][m], d[k][j] + d[j][m]);

            // 校验
            int check = 1;
            for (int j = 0; j < n; j ++ ) {
                for (int k = 0; k < n; k ++ ) {
                    if (del[j] || del[k]) continue;
                    if (d[j][k] == 0x3f3f3f3f || d[j][k] > maxDistance) check = 0;
                }
            }

            res += check;
        }
        return res;
    }
};

原文地址：https://blog.csdn.net/yl_puyu/article/details/140481017

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！