bzoj2429 [HAOI2006]聪明的猴子

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<string>
 5 #include<cstring>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<ctime>
 9 #include<queue>
10 #include<stack>
11 #include<map>
12 #include<set>
13 using namespace std;
14 int getint()
15 {
16     int ret=0,f=1;
17     char ch=getchar();
18     while(ch<‘0‘||ch>‘9‘)
19     {
20         if(ch==‘-‘)f=0;
21         ch=getchar();
22     }
23     while(ch>=‘0‘&&ch<=‘9‘)ret*=10,ret+=ch-‘0‘,ch=getchar();
24     return f==0?-ret:ret;
25 }
26 struct bian
27 {
28     int x,y,v;
29     bool operator < (const bian &a)const
30     {
31         return v<a.v;
32     }
33 }bi[500050];
34 int Max,n,m,ed,ans,tot,a[555],x[1010],y[1010],fa[1010];
35 int find(int x)
36 {
37     return x==fa[x]?x:fa[x]=find(fa[x]);
38 }
39 int main()
40 {
41     n=getint();
42     for(int i=1;i<=n;i++)a[i]=getint();
43     m=getint();
44     for(int i=1;i<=m;i++)fa[i]=i,x[i]=getint(),y[i]=getint();
45     for(int i=1;i<=m;i++)
46         for(int j=i+1;j<=m;j++)
47             bi[++ed].x=i,bi[ed].y=j,bi[ed].v=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
48     sort(bi+1,bi+ed+1);
49     for(int i=1;i<=ed;i++)
50     {
51         int q=find(bi[i].x),w=find(bi[i].y);
52         if(q!=w)
53         {
54             fa[q]=w;
55             tot++;
56             if(tot==m-1)
57             {
58                 Max=bi[i].v;
59                 break;
60             }
61         }
62     }
63     for(int i=1;i<=n;i++)if(a[i]*a[i]>=Max)ans++;
64     printf("%d",ans);
65     return 0;
66 }