40分求助!!回复必关
查看原帖
40分求助!!回复必关
524906
刘辰雨楼主2023/3/26 21:09

RT

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;
const long long maxn = 501;
const long long maxm = 250001;

long long fa[maxn];
long long find(long long x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
struct node {
	long long first, second;
	double value;
}edge[maxm];
struct point {
	long long x, y;
}p[maxn];
bool operator < (node a, node b) {
	return a.value < b.value;
}
long long out[maxm], cnt;
bitset<maxn> vist;

long long n, m, s;

int main() {
	scanf("%lld%lld", &s, &n);
	for(long long i = 1 ; i<= n ; i++) {
		scanf("%lld%lld", &p[i].x, &p[i].y);
		fa[i] = i;
	}
	for(long long i = 1 ; i<= n ; i++) {
		for(long long j = i+1 ; j<= n ; j++) {
			edge[++m].first = i;
			edge[m].second = j;
			edge[m].value = (double)sqrt((1.0*p[i].x-p[j].x)*(p[i].x-p[j].x)+(1.0*p[i].y-p[j].y)*(p[i].y-p[j].y));
		}
	}
	sort(edge+1, edge+m+1);
	for(long long i = 1 ; i<= n ; i++) {
		if(find(edge[i].first) == find(edge[i].second)) {
			continue;
		}
		fa[find(edge[i].first)] = find(edge[i].second);
		out[++cnt] = i;
		if(cnt == n-s) {
			printf("%.2lf\n", edge[i].value);
		}
	}
	return 0;
}
2023/3/26 21:09
加载中...