admin管理员组

文章数量:1581095

原题传送门
最小生成树，若有 k k k个手机，那么可以让 k k k个连通块连起来
所以从小建边，只剩 k k k个连通块时就输出

Code：

#include <bits/stdc++.h>
#define maxn 1010
#define maxm 1000010
using namespace std;
const double eps = 1e-5;
struct Line{
	int x, y;
	double len;
}line[maxm], len[maxm];
int x[maxn], y[maxn], f[maxn], vis[maxn], n, m, tot, cnt;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = 1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool cmp(Line x, Line y){ return x.len < y.len; }
int getfa(int k){ return f[k] == k ? k : f[k] = getfa(f[k]); }

int main(){
	freopen("wireless.in", "r", stdin);
	freopen("wireless.out", "w", stdout);
	m = read(), n = read();
	for (int i = 1; i <= n; ++i){
		x[i] = read(), y[i] = read();
		for (int j = 1; j < i; ++j) line[++tot] = (Line){j, i, (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])};
	}
	sort(line + 1, line + 1 + tot, cmp);
	for (int i = 1; i <= n; ++i) f[i] = i;
	for (int i = 1; i <= tot; ++i){
		int x = getfa(line[i].x), y = getfa(line[i].y);
		if (x != y){
			f[x] = y, len[++cnt] = line[i];
			if (n - cnt <= m) return printf("%.2lf\n", sqrt(len[cnt].len)), 0;
		}
	}
	return 0;
}

本文标签： 通讯网题解

版权声明：本文标题：【题解】LuoGu1991：无线通讯网 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1727878380a1135338.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。