闻缺陷则喜何志丹

闻缺陷则喜何志丹

本文涉及知识点

图论 状态压缩 枚举 多源路径

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;
	}
};

【图论 状态压缩 枚举】2959. 关闭分部的可行集合数目-LMLPHP

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。

【图论 状态压缩 枚举】2959. 关闭分部的可行集合数目-LMLPHP

04-09 08:52