題目描述
在一個熱帶雨林中生存著一群猴子，它們以樹上的果子為生。昨天下了一場大雨，現在雨過天晴，但整個雨林的地表還是被大水淹沒著，部分植物的樹冠露在水面上。猴子不會游泳，但跳躍能力比較強，它們仍然可以在露出水面的不同樹冠上來回穿梭，以找到喜歡吃的果實。
現在，在這個地區露出水面的有N棵樹，假設每棵樹本身的直徑都很小，可以忽略不計。我們在這塊區域上建立直角坐標系，則每一棵樹的位置由其所對應的坐標表示(任意兩棵樹的坐標都不相同)。
在這個地區住著的猴子有M個，下雨時，它們都躲到了茂密高大的樹冠中，沒有被大水沖走。由于各個猴子的年齡不同、身體素質不同，它們跳躍的能力不同。有的猴子跳躍的距離比較遠(當然也可以跳到較近的樹上)，而有些猴子跳躍的距離就比較近。這些猴子非常聰明，它們通過目測就可以準確地判斷出自己能否跳到對面的樹上。
【問題】現已知猴子的數量及每一個猴子的最大跳躍距離，還知道露出水面的每一棵樹的坐標，你的任務是統計有多少個猴子可以在這個地區露出水面的所有樹冠上覓食。
輸入格式
輸入文件monkey.in包括：
第1行為一個整數，表示猴子的個數M(2<=M<=500)；
第2行為M個整數，依次表示猴子的最大跳躍距離（每個整數值在1--1000之間）；
第3行為一個整數表示樹的總棵數N(2<=N<=1000)；
第4行至第N+3行為N棵樹的坐標（橫縱坐標均為整數，范圍為：-1000--1000）。
（同一行的整數間用空格分開）
輸出格式
輸出文件monkey.out包括一個整數，表示可以在這個地區的所有樹冠上覓食的猴子數。
數據范圍
2≤N≤1000,1≤M≤500
思路：
這道題是一道使用最小生成樹的克魯斯卡爾算法的題。我們要用最小生成樹來將所有節點連接起來，并求出將它連接所需的最小距離。
在這道題中，我們將所有的樹冠的位置上設置為端點。在讀入的時候，我們設一個結構體來分別存儲每個端點的橫坐標和縱坐標。記錄下每一個端點后，我們可以O(n2)枚舉每兩個端點，求出這些端點中任意兩個點之間的距離（因為所有端點間都可以連接，所以我們可以直接構造一個完全圖），并且再開一個結構體來存儲每一條邊的起點、終點和距離。接下來，我們要對邊權從小到大進行排序。
我們維護一個對每個端點的并查集，從邊權從小到大加入邊，直到邊數足夠即可退出循環。在建最小生成樹的時候，我們要不斷更新最小生成樹中的最長邊的長度。因為我們已經對邊權進行了從小到大的排序，所以后加入的邊邊權一定比前加入的邊邊權大，故在更新最值時不用比較。
最后求出最值后，我們再對猴子的最大跳躍距離從大到小進行排序，然后進行O(n)的從前往后枚舉，如果枚舉到一只猴子最大距離小于最大邊權，則退出枚舉，同時輸出當前猴子的序號減1的值（從當前猴子開始無法全跳過）。或者如果已經枚舉到了最后一只猴子，則只需要輸出這只猴子序號即可，因為所有猴子都能到達所有樹冠。
這里不需要判斷能否建成最小生成樹，因為我們建圖時建立的是完全圖，保證每兩點間都能聯通。
另外，在求和判斷距離時我們不必求出實際距離，而是求出實際距離的平方，同時在讀入猴子最大跳躍距離時對其取平方，這樣可以避免精度問題和類型轉換。
最后是完整代碼：
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 int m;
5 int dis[505];
6 int n;
7 struct tree{
8 int x,y;
9 }a[1005];
10 int fa[1005];
11 struct street{
12 int start;
13 int end;
14 int val;
15 }b[1000005];
16 bool cmp(street a,street b){
17 return a.val<b.val;
18 }
19 bool cmp2(int a,int b){
20 return a>b;
21 }
22 int find(int x){
23 if(x==fa[x]){
24 return x;
25 }else{
26 return fa[x]=find(fa[x]);
27 }
28 }
29 void unionn(int x,int y){
30 int r1=find(x);
31 int r2=find(y);
32 fa[r1]=r2;
33 }
34 int main(){
35 cin>>m;
36 for(int i=1;i<=m;i++){
37 cin>>dis[i];
38 }
39 sort(dis+1,dis+m+1,cmp2);//從大到小排序
40 cin>>n;
41 for(int i=1;i<=n;i++){
42 cin>>a[i].x>>a[i].y;
43 }
44 int cnt=1;
45 for(int i=1;i<=n;i++){
46 for(int j=i+1;j<=n;j++){
47 b[cnt].start=i;
48 b[cnt].end=j;
49 b[cnt].val=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
50 cnt++;
51 }
52 }
53 cnt--;
54 sort(b+1,b+cnt+1,cmp);
55 for(int i=1;i<=n;i++){
56 fa[i]=i;
57 }
58 int sum=0;
59 int ans=-9999;//加入最小生成樹的邊的邊權最大值
60 for(int i=1;i<=cnt;i++){
61 if(find(b[i].start)!=find(b[i].end)){
62 sum++;
63 ans=max(ans,b[i].val);
64 unionn(b[i].start,b[i].end);
65 }
66 if(sum==n-1){
67 break;
68 }
69 }
70 for(int i=1;i<=m;i++){
71 if(dis[i]*dis[i]<ans){
72 cout<<i-1<<endl;
73 break;
74 }
75 if(i==m){
76 cout<<m<<endl;
77 break;
78 }
79 }
80 return 0;
81 }
浙公網安備 33010602011771號