本文涉及知识点
图论 状态压缩 枚举 多源路径
LeetCode2959. 关闭分部的可行集合数目
一个公司在全国有 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
一开始所有分部之间通过道路互相可以到达。
多源路径
枚举所有没关闭的分部，共2n种可能。
每种可能最多10个节点，利用Flod 求多源路径，时间复杂度O(nnn)。
故总时间复杂度O(2nnnn)。
代码
//多源码路径 template<class T, T INF = 1000 * 1000 * 1000> class CFloyd { public: CFloyd(const vector<vector<T>>& mat) { m_vMat = mat; const int n = mat.size(); for (int i = 0; i < n; i++) {//通过i中转 for (int i1 = 0; i1 < n; i1++) { if (INF == m_vMat[i1][i]) { continue; } for (int i2 = 0; i2 < n; i2++) { //此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离 m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]); //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离 } } } }; vector<vector<T>> m_vMat; }; class Solution { public: int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) { int iRet = 0; for (int iMask = 0; iMask < (1 << n); iMask++) { iRet += Do(iMask, n, maxDistance, roads); } return iRet; } bool Do(int iMask, int n, int maxDistance, vector<vector<int>>& roads) { vector<vector<int>> mat(n, vector<int>(n, 1000'000'000)); for (int i = 0; i < n; i++) { mat[i][i] = 0; } for (const auto& v : roads) { if ((iMask & (1 << v[0])) && (iMask & (1 << v[1]))) { mat[v[1]][v[0]] = mat[v[0]][v[1]] = min(mat[v[0]][v[1]], v[2]); } } CFloyd<int> floyd(mat); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if ((iMask & (1 << i)) && (iMask & (1 << j))) { if (floyd.m_vMat[i][j] > maxDistance) { return false; } } } } return true; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { int n, maxDistance; vector<vector<int>> roads; { n = 3, maxDistance = 12, roads = { {1, 0, 11},{1, 0, 16},{0, 2, 13} }; auto res = Solution().numberOfSets(n, maxDistance, roads); Assert(5, res); } { n = 3, maxDistance = 5, roads = { {0,1,2},{1,2,10},{0,2,10} }; auto res = Solution().numberOfSets(n, maxDistance, roads); Assert(5 , res); } //CConsole::Out(res); }
优化了封装类
template<class T = int > class CFloyd { public: CFloyd(int n, const T INF = 1000 * 1000 * 1000):m_INF(INF) { m_vMat.assign(n, vector<T>(n, m_INF)); for (int i = 0; i < n; i++) { m_vMat[i][i] = 0; } } void SetEdge(int i1, int i2,const T& dis, bool bDirect = false) { m_vMat[i1][i2] = min(m_vMat[i1][i2],dis); if (!bDirect) { m_vMat[i2][i1] = m_vMat[i1][i2]; } } vector<vector<T>> Dis() { auto vResMat = m_vMat; const int n = m_vMat.size(); for (int i = 0; i < n; i++) {//通过i中转 for (int i1 = 0; i1 < n; i1++) { if (m_INF == vResMat[i1][i]) { continue; } for (int i2 = 0; i2 < n; i2++) { //此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离 vResMat[i1][i2] = min(vResMat[i1][i2], vResMat[i1][i] + vResMat[i][i2]); //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离 } } } return vResMat; }; vector<vector<T>> m_vMat;//结果串 const T m_INF; }; class Solution { public: int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) { int iRet = 0; for (int iMask = 0; iMask < (1 << n); iMask++) { iRet += Do(iMask, n, maxDistance, roads); } return iRet; } bool Do(int iMask, int n, int maxDistance, vector<vector<int>>& roads) { CFloyd<int> floyd(n); for (const auto& v : roads) { if ((iMask & (1 << v[0])) && (iMask & (1 << v[1]))) { floyd.SetEdge(v[0],v[1],v[2]); } } auto res = floyd.Dis(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if ((iMask & (1 << i)) && (iMask & (1 << j))) { if (res[i][j] > maxDistance) { return false; } } } } return true; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
