最小生成樹 2429: [HAOI2006]聰明的猴子

BZOJ 2429: [HAOI2006]聰明的猴子

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 877  Solved: 566

[Submit][Status][Discuss]

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

對于40%的資料，保證有2<=N <=100，1<=M<=100

對于全部的資料，保證有2<=N <= 1000，1<=M=500

/*
思路：這個題目還是比較明顯的，因為最小生成樹的性質滿足最大邊最小，“能所有樹冠上覓食”，是以一定這個猴子一定可以經過最小生成樹的最大邊，因為沒有其他更小的距離來把全部的樹都走一遍了。
隻需記錄最小生成樹的最大邊，統計有多少隻猴子能夠跨越這個最大邊即可。
*/      

1 /*kruskal算法過程：建完邊之後，把所有邊從小到大拍一個序，按這個順序往最小生成樹裡面加邊，用并查集維護關系。*/
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<iostream>
 5 using namespace std;
 6 #include<cstdio>
 7 #define N 1005
 8 #define M 505
 9 int t,n,m,dist[M],father[N];
10 struct Zb{
11     int x,y;
12 }zb[N];
13 struct Edge{
14     int u,v;
15     double w;
16     bool operator<(Edge Q)
17     const{return w<Q.w;}
18 }edge[N*N];
19 double ans;
20 void input()
21 {
22     scanf("%d",&m);
23     for(int i=1;i<=m;++i)
24     {
25         scanf("%d",&dist[i]);
26     }
27     scanf("%d",&n);
28     for(int i=1;i<=n;++i)
29     {
30         scanf("%d%d",&zb[i].x,&zb[i].y);
31     }
32 }
33 void add_edge(int a,int b)
34 {
35     ++t;
36     edge[t].u=a;edge[t].v=b;
37     edge[t].w=sqrt((zb[a].x-zb[b].x)*(zb[a].x-zb[b].x)+(zb[a].y-zb[b].y)*(zb[a].y-zb[b].y));
38 }
39 void build_edge()
40 {
41     for(int i=1;i<=n;++i)
42       for(int j=i+1;j<=n;++j)
43       {
44           add_edge(i,j);
45       }
46 }
47 int find(int x)
48 {
49     return(father[x]==x?x:father[x]=find(father[x]));
50 }
51 void kruskal()
52 {
53     for(int i=1;i<=n;++i)  father[i]=i;
54     sort(edge+1,edge+t+1);
55     int num=0;
56     for(int l=1;l<=t;++l)
57     {
58         int x1=find(edge[l].u);
59         int y1=find(edge[l].v);
60         if(x1==y1) continue;
61         num++;
62         father[y1]=x1;
63         if(num==n-1)
64         {
65             ans=edge[l].w;
66             break;
67         }
68     }
69 }
70 int main()
71 {
72     input();
73     build_edge();
74     kruskal();
75     int ret=0;
76     for(int i=1;i<=m;++i)
77     {
78         if(dist[i]>=ans) ret++;
79     }
80     printf("%d",ret);
81     return 0;
82 }