本文主要是介绍moocast(usaco2016年12月金组第1题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
题目描述
输入
输出
样例输入 复制
样例输出 复制
提示
代码
题目描述
农民约翰的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;
}
这篇关于moocast(usaco2016年12月金组第1题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!