题目

Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.

思路

将已经连接上的点放进同一个并查集中，再用kruskal生成MST，判断条件由一般kruskal的edgeSelected<n-1调整为到图连通为止。

• 能用double就不用float，否则造成精度丢失
• 放进同一个并查集的时候用root[find(a)]=find(b)，而不是简单的root[a]=b]，因为不能确保已知的每条边都连两个新的独立顶点

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1001
#define INF 999999999
//int cost[MAXN][MAXN];

typedef struct ms
{
	double x, y;
}point;

typedef struct ed
{
	int u, v;
	double w;
}edge;

point cord[MAXN];
int root[MAXN] = { 0 };
vector<edge> Edges;


double compDis(point a, point b)
{
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}

bool cmp(edge a, edge b)
{
	return a.w < b.w;
}

int find(int x)
{
	int tmp = x;
	while (root[tmp] != tmp)
	{
		tmp = root[tmp];
	}

	int k = x;
	while (k != tmp)
	{
		int j = root[k];
		root[k] = tmp;
		k = j;
	}

	return tmp;
}

void join(int x, int y)
{
	int rootx = find(x);
	int rooty = find(y);
	if (rootx != rooty)
	{
		root[rootx] = rooty;
	}
}

bool isConnect(int root[], int n)
{
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		if (root[i] == i)
		{
			cnt++;
		}
	}
	if (cnt != 1) return false;
	return true;
}

int main()
{
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		double x, y; cin >> x >> y;
		cord[i] = point{ x,y };
	}

	for (int i = 1; i <= n; i++)
	{
		root[i] = i;
	}

	for (int i = 0; i < m; i++)
	{
		int a, b; cin >> a >> b;
		join(find(a), find(b));
	}

	for (int i = 1; i < n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			double w = compDis(cord[i], cord[j]);
			Edges.push_back(edge{ i,j,w });
		}
	}
	sort(Edges.begin(), Edges.end(), cmp);

	int i = 0;
	double res = 0;
	while (!isConnect(root,n))
	{
		if (find(Edges[i].u) != find(Edges[i].v))
		{
			// cout << Edges[i].u << ' ' << Edges[i].v << ' ' << Edges[i].w << endl;
			join(find(Edges[i].u), find(Edges[i].v));
			res += Edges[i].w;
		}
		i++;
	}

	cout.setf(ios::fixed);
	cout << setprecision(2) << res << endl;

	return 0;
}