本文涉及知识点
图论 状态压缩 枚举 多源路径
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 <= 10
0 <= roads.length <= 1000
roads[i].length == 3
0 <= ui, vi <= n - 1
ui != vi
1 <= wi <= 1000
一开始所有分部之间通过道路互相可以到达。
多源路径
枚举所有没关闭的分部，共2种可能。
每种可能最多10个节点，利用Flod 求多源路径，时间复杂度O(nnn)。
故总时间复杂度O(2nnn)。
代码
//多源码路径
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++**实现。