【bzoj2429】[HAOI2006]聪明的猴子（图论–最小瓶颈生成树 模版题）

题意：有M只猴子，他们的最大跳跃距离为Ai。树林中有N棵树露出了水面，给出了它们的坐标。问有多少只猴子能在这个地区露出水面的所有树冠上觅食。

解法：由于要尽量多的猴子能到达所有树冠，便用Kruskal求一次MST最小生成树，也就得到了最大边最小的最小瓶颈生成树。在用这个最大边权计算合法的猴子树。

P.S.由于没有那些一下子输入几十万的数据，所以读优和不读优差别不大。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 using namespace std;
 7
 8 const int M=510,N=1010,D=2010;
 9 int n,m,len;
10 int a[M],fa[N];
11 struct node{int x,y;}b[N];
12 struct edge
13 {
14     int x,y,d;
15     edge() {}
16     edge(int i,int j,int k) {x=i;y=j;d=k;}
17 }
18 e[N*N/2];
19
20 int sq_dist(int i,int j) {return (b[i].x-b[j].x)*(b[i].x-b[j].x)+(b[i].y-b[j].y)*(b[i].y-b[j].y);}
21 bool cmp(edge x,edge y) {return x.d<y.d;}
22 int ffind(int x)
23 {
24     if (fa[x]!=x) fa[x]=ffind(fa[x]);
25     return fa[x];
26 }
27 int Kruskal()
28 {
29     int i,j,k=0;
30     for (i=1;i<=n;i++) fa[i]=i;
31     sort(e+1,e+1+len,cmp);
32     for (i=1;i<=len;i++)
33     {
34       int fx=ffind(e[i].x),fy=ffind(e[i].y);
35       if (fx!=fy)
36       {
37         fa[fx]=fy,k++;
38         if (k==n-1) return e[i].d;
39       }
40     }
41 }
42 int read()
43 {
44     char c=getchar();
45     int x=0,t=1;
46     while (c>'9'||c<'0') {if (c=='-') t=-1;c=getchar();}
47     while (c<='9'&&c>='0') {x=x*10+(c-'0');c=getchar();}
48     return x*t;
49 }
50 int main()
51 {
52     int i,j,k;
53     m=read();
54     for (i=1;i<=m;i++) a[i]=read();
55     n=read();
56     for (i=1;i<=n;i++)
57       b[i].x=read(),b[i].y=read();
58     len=0;
59     for (i=1;i<=n;i++)
60       for (j=i+1;j<=n;j++)
61         e[++len]=edge(i,j,sq_dist(i,j));
62     int mx=Kruskal(),cnt=0;
63     for (i=1;i<=m;i++)
64       if (a[i]*a[i]>=mx) cnt++;
65     printf("%d\n",cnt);
66     return 0;
67 }