自动搬运

查看原文

来自洛谷，原作者为

	奔波儿霸 **

搬运于2025-08-24 21:42:14，当前版本为作者最后更新于2018-08-08 15:09:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定$N$个点的横纵坐标。两个点之间能够连边的条件是两个点的距离小于$\sqrt{\text{花费}}$，算出能够使得所有的点都连通的最小花费。

解题思路

根本用不着二分答案嘛。直接$N^2$建边，跑一遍$Kruskal$。记录在最小生成树中的最长的一条边。显然只要使得这条边能够建立，那么这棵最小生成树中的所有的边都可以建立。答案就是最长的边的距离的平方，注意要用$double$存边权。

附上代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 1e3+3;
int n, x[maxn], y[maxn], cnt, tot, f[maxn];
double Ans;
struct Edge {
	int u, v;
	double w;
}ed[maxn * maxn];
inline bool cmp(Edge a, Edge b) {
	return a.w < b.w;
}
inline int find(int x) {
	if(x == f[x]) return x;
	else return f[x] = find(f[x]);
}
inline void Kruskal() {
	for(int i=1; i<=n; i++) f[i] = i;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i != j) {
				++cnt;
				ed[cnt].u = i, ed[cnt].v = j, ed[cnt].w = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			}
		}
	}
	sort(ed+1, ed+1+cnt, cmp);
	for(int i=1; i<=cnt; i++) {
		int xx = find(ed[i].u), yy = find(ed[i].v);
		if(xx != yy) {
			f[xx] = find(yy);
			tot ++;
			Ans = ed[i].w;
		}
		if(tot == n-1) {
			break;
		}
	}
}

int main() {
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		scanf("%d%d", &x[i], &y[i]);
	}
	Kruskal();
	printf("%.0lf", Ans * Ans);
}