题目分类：最小生成树

题意：

给出平面上n个点和m个猴子的跳跃能力，问哪些猴子能跳到所有的树上。

题解：

求出最小生成树，然后将猴子跳跃能力和最大边作比较。

程序：

#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
int fat[1200];
inline int fnd(int x)
{
	if(fat[x]==x)return x;
	return fat[x]=fnd(fat[x]);
}
int n,cnt,xx[1200],yy[1200],jum[1200],m;
pair<int,pair<int,int> >a[1200000];
inline int sqr(int x)
{
	return x*x;
}
int ans,res;
int main()
{
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d",&jum[i]);
	}
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d %d",&xx[i],&yy[i]);
	}
	for (int i=1;i<n;i++)
	{
		fat[i]=i;
		for (int j=i+1;j<=n;j++)
		{
			cnt++;
			a[cnt].second.first=i;
			a[cnt].second.second=j;
			a[cnt].first=sqr(xx[i]-xx[j])+sqr(yy[i]-yy[j]);
		}
	}
	sort(a+1,a+cnt+1);
	for (int i=1;i<=cnt;i++)
	{
		int x1=a[i].second.first,x2=a[i].second.second;
		if(fnd(x1)!=fnd(x2))
		{
			ans=a[i].first;
			fat[fnd(x1)]=fnd(x2);
		}
	}
	for (int i=1;i<=m;i++)
	{
		if(ans<=sqr(jum[i]))res++;
	}printf("%d\n",res);
	return 0;
}