只得了十分,求大佬看一下啊!!!
查看原帖
只得了十分,求大佬看一下啊!!!
1032056
huzhehan楼主2023/12/24 16:07
#include <bits/stdc++.h>
using namespace std;
int n, m;
double yr[10005];

struct node {
	int s1;
	int s2;
	double wi;
} e[500005];
int k;
int fa[50005];
int ans;

int find(int x) {
	if (x != fa[x]) {
		return fa[x] = find(fa[x]);
	} else {
		return x;
	}
}

bool cmp(node x, node y) {
	return x.wi < y.wi;
}

void Union(int x, int y) {
	fa[find(x)] = find(y);
}

bool judge(int x, int y) {
	return find(x) == find(y);
}

int cnt;

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

		cin >> x[i] >> y[i];
	}
	for (int i = 1; i <= m; i++) {
		for (int j = i + 1; j <= m; j++) {


			if ( i < j) {
				double ww = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
				e[++cnt].s1 = i;
				e[cnt].s2 = j;
				e[cnt].wi = ww;
			}
		}
	}
	for (int i = 1; i <= m; i++)
	{
		fa[i] = i;
	}
	sort(e + 1, e + 1 + cnt, cmp);

	for (int i = 1; i <= cnt; i++) {
		if (find(e[i].s1) == find(e[i].s2)) 
		{
			continue;
		}
		Union(e[i].s1, e[i].s2);
		k++;
		if (k == n - m + 1)
		{
			printf("%.2f", e[i].wi);

			return 0;
		}

	}


	return 0;
}
2023/12/24 16:07
加载中...