给定的二维平面上的N个节点表示为（x i，y i）。如果节点之间的曼哈顿距离为1，则称这些节点已连接。您可以连接两个未连接的节点，而这两个节点之间的距离是欧式距离。任务是连接图，以使每个节点都有一条从任何节点到其路径的路径，且成本最低。

例子：

Input: N = 3, edges[][] = {{1, 1}, {1, 1}, {2, 2}, {3, 2}}
Output: 1.41421
Since (2, 2) and (2, 3) are already connected.
So we try to connect either (1, 1) with (2, 2)
or (1, 1) with (2, 3) but (1, 1) with (2, 2)
yields the minimum cost.
Input: N = 3, edges[][] = {{1, 1}, {2, 2}, {3, 3}}
Output: 2.82843

方法：蛮力的方法是每个节点与所有其他节点和类似的其他连接ñ节点，但在时间复杂度将是最坏的情况下ñ ñ。

另一种方法是找到具有欧几里得距离的每对顶点的成本，并且那些相连的对的成本为0。

在知道每一对的代价之后，我们将对最小生成树应用Kruskal算法，它将产生连接图的最小代价。请注意，对于Kruskal算法，您必须具有不相交集并集（DSU）的知识。

下面是上述方法的实现：

// C++ implentation of the approach 
#include <bits/stdc++.h> 
using namespace std; 
// Max number of nodes given 
const int N = 500 + 10; 
// arr is the parent array 
// sz is the size of the 
// subtree in DSU 
int arr[N], sz[N]; 
// Function to initilize the parent 
// and size array for DSU 
void initialize() 
{ 
	for (int i = 1; i < N; ++i) { 
		arr[i] = i; 
		sz[i] = 1; 
	} 
} 
// Function to return the 
// parent of the node 
int root(int i) 
{ 
	while (arr[i] != i) 
		i = arr[i]; 
	return i; 
} 
// Function to perform the 
// merge operation 
void unin(int a, int b) 
{ 
	a = root(a); 
	b = root(b); 
	if (a != b) { 
		if (sz[a] < sz[b]) 
			swap(a, b); 
		sz[a] += sz[b]; 
		arr[b] = a; 
	} 
} 
// Function to return the minimum cost required 
double minCost(vector<pair<int, int> >& p) 
{ 
	// Number of points 
	int n = (int)p.size(); 
	// To store the cost of every possible pair 
	// as { cost, {to, from}}. 
	vector<pair<double, pair<int, int> > > cost; 
	// Calculating the cost of every possible pair 
	for (int i = 0; i < n; ++i) { 
		for (int j = 0; j < n; ++j) { 
			if (i != j) { 
				// Getting Manhattan distance 
				int x = abs(p[i].first - p[j].first) 
						+ abs(p[i].second - p[j].second); 
				// If the distance is 1 the cost is 0 
				// or already connected 
				if (x == 1) { 
					cost.push_back({ 0, { i + 1, j + 1 } }); 
					cost.push_back({ 0, { j + 1, i + 1 } }); 
				} 
				else { 
					// Calculating the euclidean distance 
					int a = p[i].first - p[j].first; 
					int b = p[i].second - p[j].second; 
					a *= a; 
					b *= b; 
					double d = sqrt(a + b); 
					cost.push_back({ d, { i + 1, j + 1 } }); 
					cost.push_back({ d, { j + 1, i + 1 } }); 
				} 
			} 
		} 
	} 
	// Krushkal Algorithm for Minimum 
	// spanning tree 
	sort(cost.begin(), cost.end()); 
	// To initialize the size and 
	// parent array 
	initialize(); 
	double ans = 0.00; 
	for (auto i : cost) { 
		double c = i.first; 
		int a = i.second.first; 
		int b = i.second.second; 
		// If the parents are different 
		if (root(a) != root(b)) { 
			unin(a, b); 
			ans += c; 
		} 
	} 
	return ans; 
} 
// Driver code 
int main() 
{ 
	// Vector pairs of points 
	vector<pair<int, int> > points = { 
		{ 1, 1 }, 
		{ 2, 2 }, 
		{ 2, 3 } 
	}; 
	// Function calling and printing 
	// the answer 
	cout << minCost(points); 
	return 0; 
}

输出：

1.41421

本文链接:http://www.it72.com/12630.htm