聪明的猴子 黑暗爆炸 - 2429
Description
在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地
表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面
的不同树冠上来回穿梭，以找到喜欢吃的果实。现在，在这个地区露出水面的有N棵树，假设每棵树本身的直径都
很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树
的坐标都不相同)。在这个地区住着的猴子有M个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由
于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近
的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到
对面的树上。【问题】 现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你
的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。
Input
第1行为一个整数，表示猴子的个数M(2<=M<=500)；
第2行为M个整数，依次表示猴子的最大跳跃距离（每个整数值在1--1000之间）；
第3行为一个整数表示树的总棵数N(2<=N<=1000)；
第4行至第N+3行为N棵树的坐标（横纵坐标均为整数，范围为：-1000--1000）。
（同一行的整数间用空格分开）
Output
包括一个整数，表示可以在这个地区的所有树冠上觅食的猴子数
Sample Input
4
1 2 3 4
6
0 0
1 0
1 2
-1 -1
-2 0
2 2
Sample Output
3
Hint
2<=N <= 1000，1<=M=500
最小生成树首先选择边最小的边，所以当实现一棵最小生成树后，可知该树中最大的边，若猴子的跳跃距离大于最大边，则猴子可以跳跃所有的树，反之不能
由此可知，本题就是最小生成树的模板题
建图，遍历所有的点，勾股定理求出距离
AC代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=510;
const int M=1010;
struct Node{
int x,y;int w;
}node[(M-1)*M/2];
int n;
int p[N];
int m;
int x[M],y[M];
int k;
int f[M];
int maxl;bool cmp(Node a,Node b)
{
return a.w<b.w;
}double Dist(int a,int b,int c,int d)
{
return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}int find(int a)
{
if(f[a]!=a) f[a]=find(f[a]);return f[a];
}void kruskal()
{
sort(node,node+k,cmp);for(int i=1;i<=m;i++) f[i]=i;int cnt=m-1;for(int i=0;i<k;i++){
int a=node[i].x;int b=node[i].y;int w=node[i].w;if(find(a)!=find(b)){
f[find(a)]=find(b);cnt--;if(w>maxl) maxl=w;}}
}int main()
{
cin>>n;for(int i=1;i<=n;i++) cin>>p[i];cin>>m; for(int i=1;i<=m;i++){
cin>>x[i]>>y[i];for(int j=1;j<i;j++){
node[k].x=i;node[k].y=j;node[k].w=Dist(x[i],y[i],x[j],y[j]);k++;}}kruskal();int ans=0;for(int i=1;i<=n;i++)if(p[i]>=maxl) ans++;cout<<ans<<endl; return 0;
}