本文涉及知识点

C++图论

LeetCode1584. 连接所有点的最小费用

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
示例 1：

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：
我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
示例 2：

输入：points = [[3,12],[-2,5],[-4,1]]
输出：18
示例 3：

输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4
示例 4：

输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000
示例 5：

输入：points = [[0,0]]
输出：0

提示：
1 <= points.length <= 1000
-10⁶ <= xi, yi <= 10⁶
所有点 (xi, yi) 两两不同。

代码

核心代码

class CNearestMST
{
public:
	CNearestMST(const int iNodeSize) :m_bDo(iNodeSize), m_vDis(iNodeSize, INT_MAX), m_vNeiTable(iNodeSize)
	{

	}
	void Init(const vector<vector<int>>& edges)
	{
		for (const auto& v : edges)
		{
			Add(v);
		}
	}
	void Add(const vector<int>& v)
	{
		m_vNeiTable[v[0]].emplace_back(v[1], v[2]);
		m_vNeiTable[v[1]].emplace_back(v[0], v[2]);
	}
	int MST(int start)
	{
		int next = start;
		while ((next = AddNode(next)) >= 0);
		return m_iMST;
	}
	int MST(int iNode1, int iNode2, int iWeight)
	{
		m_bDo[iNode1] = true;
		for (const auto& it : m_vNeiTable[iNode1])
		{
			if (m_bDo[it.first])
			{
				continue;
			}
			m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);
		}
		m_iMST = iWeight;

		int next = iNode2;
		while ((next = AddNode(next)) >= 0);
		return m_iMST;
	}

private:
	int AddNode(int iCur)
	{
		m_bDo[iCur] = true;
		for (const auto& it : m_vNeiTable[iCur])
		{
			if (m_bDo[it.first])
			{
				continue;
			}
			m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);
		}

		int iMinIndex = -1;
		for (int i = 0; i < m_vDis.size(); i++)
		{
			if (m_bDo[i])
			{
				continue;
			}
			if ((-1 == iMinIndex) || (m_vDis[i] < m_vDis[iMinIndex]))
			{
				iMinIndex = i;
			}
		}
		if (-1 != iMinIndex)
		{
			if (INT_MAX == m_vDis[iMinIndex])
			{
				m_iMST = -1;
				return -1;
			}
			m_iMST += m_vDis[iMinIndex];
		}

		return iMinIndex;
	}
	vector<bool> m_bDo;
	vector<long long> m_vDis;
	vector < vector<std::pair<int, int>>> m_vNeiTable;
	long long m_iMST = 0;
};

class Solution {
		public:
			int minCostConnectPoints(vector<vector<int>>& points) {
				const int N = points.size();
				CNearestMST mst(N);
				for (int i = 0; i < N; i++) {
					for (int j = i + 1; j < N; j++) {
						const int iDis = abs(points[i][0] - points[j][0])+ abs(points[i][1] - points[j][1]);
						mst.Add({i,j,iDis });
					}
				}
				return mst.MST(0);
			}
		};

代码

vector<vector<int>> points;
		TEST_METHOD(TestMethod11)
		{
			points = { {0,0},{2,2},{3,10},{5,2},{7,0} };
			auto res = Solution().minCostConnectPoints(points);
			AssertEx(20, res);
		}
		TEST_METHOD(TestMethod12)
		{
			points = { {3,12},{-2,5},{-4,1} };
			auto res = Solution().minCostConnectPoints(points);
			AssertEx(18, res);
		}
		TEST_METHOD(TestMethod13)
		{
			points = { {0,0},{1,1},{1,0},{-1,1} };
			auto res = Solution().minCostConnectPoints(points);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod14)
		{
			points = { {-1000000,-1000000},{1000000,1000000} };
			auto res = Solution().minCostConnectPoints(points);
			AssertEx(4000000, res);
		}
		TEST_METHOD(TestMethod15)
		{
			points = { {0,0}};
			auto res = Solution().minCostConnectPoints(points);
			AssertEx(0, res);
		}