90,TLE一个点,求指点
查看原帖
90,TLE一个点,求指点
660776
ananran998楼主2023/1/10 14:03
#include <bits/stdc++.h>
using namespace std;
struct node {
	double x, y;
} a[501];
struct node2 {
	int n1, n2;
	double s;
	bool operator < (const node2 &A) const {
		return s < A.s;
	}
} b[250001];

int n, k, cnt = 0;
int fa[501];

double dis(int i, int j) {
	return sqrt((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y));
}

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

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%lf%lf", &a[i].x, &a[i].y);
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++) {
			b[++cnt].n1 = i;
			b[cnt].n2 = j;
			b[cnt].s = dis(i ,j);
		}
	sort(b + 1, b + cnt + 1);
	int ops = 0;
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	double ans;
	for (int i = 1; i <= cnt ;i++) {
		int h1 = b[i].n1, h2 = b[i].n2;
		int hh1 = find(h1), hh2 = find(h2);
		if (hh1 != hh2) {
			fa[hh1] = hh2;
			++ops;
		}
		if (ops == n - k + 1) {
			ans = b[i].s;
			break;
		}
	}
	printf("%.2lf\n", ans);
	return 0;
}
2023/1/10 14:03
加载中...