目录
题目描述
农民约翰的N只奶牛（1≤N≤1000）想要组织一个紧急的“moo-cast”系统，用于在他们之间广播重要的信息。牛决定装备对讲机，每个牛一个。 这些对讲机每个都具有有限的传输半径，但是奶牛可以沿着由几个跳跃组成的路径，通过中继发送到别的奶牛。因此每个奶牛不必直接传送到每个其他奶牛。
奶牛需要决定在他们的对讲机上花多少钱。 如果他们花费$ X，他们将获得一个能够传输距离为 √X的对讲机。也就是说，两头牛之间的距离的平方至多为X，才能够传到消息。
请帮助奶牛确定X的最小整数值，以便来自任何奶牛的广播将最终能够到达每个其他奶牛。
输入
输入文件名为moocast.in。
输入文件第一行输入包含一个整数N。接下来的N行，每行包含每只牛的x和y坐标。 这些都是0 ... 25,000范围内的整数。
输出
输出文件名为moocast.out。
输出文件共一行，表示X的最小整数值。
样例输入 复制
4
1 3
5 4
7 2
6 1
样例输出 复制
17提示
【数据说明】
1<=n<=1000
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,i,fx,fy,ma,f[500010],t,b,c,d,x[1000010],y[1000010],j;
struct no{int x,y,z;}a[1000010];
bool cmp(no q,no h){return q.z<h.z;}
int find(int x){if(x==f[x]) return x;return f[x]=find(f[x]);}
main(){
cin>>n;
for(i=1;i<=n;i++)cin>>x[i]>>y[i],f[i]=i;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++){t++;a[t].x=i;a[t].y=j;a[t].z=abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]);}
sort(a+1,a+1+t,cmp);
for(i=1;i<=t;i++){
fx=find(a[i].x);fy=find(a[i].y);
if(fx!=fy)f[fy]=fx,ma=max(ma,a[i].z);
}
cout<<ma;
}
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,i,fx,fy,ma,f[500010],t,b,c,d,x[1000010],y[1000010],j;
struct no{int x,y,z;}a[1000010];
bool cmp(no q,no h){return q.z<h.z;}
int find(int x){if(x==f[x]) return x;return f[x]=find(f[x]);}
main(){
cin>>n;
for(i=1;i<=n;i++)cin>>x[i]>>y[i],f[i]=i;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++){t++;a[t].x=i;a[t].y=j;a[t].z=abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]);}
sort(a+1,a+1+t,cmp);
for(i=1;i<=t;i++){
fx=find(a[i].x);fy=find(a[i].y);
if(fx!=fy)f[fy]=fx,ma=max(ma,a[i].z);
}
cout<<ma;
}
