HAOI2006-2-2 聰明的猴子解題報告 | 宁心勉学，慎思笃行

文章目錄

問題描述

在一個熱帶雨林中生存著一群猴子，它們以樹上的果子為生。昨天下了一場大雨，現在雨過天晴，但整個雨林的地表還是被大水淹沒著，部分植物的樹冠露在水面上。猴子不會游泳，但跳躍能力比較強，它們仍然可以在露出水面的不同樹冠上來回穿梭，以找到喜歡吃的果實。

現在，在這個地區露出水面的有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包括一個整數，表示可以在這個地區的所有樹冠上覓食的猴子數。

樣例

若輸入文件monkey.in中的內容為：

4 1 2 3 4 6 0 0 1 0 1 2 -1 -1 -2 0 2 2

則輸出文件monkey.out中的內容應為：

3

數據規模

對於40%的數據，保證有2<=N <=100，1<=M<=100 對於全部的數據，保證有2<=N <= 1000，1<=M=500

問題分析

這個問題是一個經典的圖論問題。分析題目可以知道，這道題的數據範圍比較大，如果使用搜索去求解肯定會超時。

仔細研究題目可以發現，所要求的是「必須能夠到所有樹冠上覓食的猴子數」，也就是說，把每個數當作座標系上的一個點的話，那麼每個點都要至少經過一次。如果我們能夠求解出一個最小生成樹，那麼，由 Prim 算法可以知道，每次所選取的邊，都是要走過所有點時，所需要經過的最短的邊的集合中的一條。

因此，如果我們可以找出這個圖的一條最小生成樹，那麼只要一個猴子能夠跳過這個最小生成樹中最長的一條邊，那麼它就一定可以到達所有的點，也就可以滿足題目的要求。

綜上所述，本題的算法應該這樣設計：

初始化，讀入數據。
利用 Prim 算法試圖求出一個最小生成樹，並在求生成樹的過程中隨時更新已經加入生成樹中的最長邊的長度Lmax。由於這道題目的所有樹冠之間都是連通的，所以使用該算法一定可以得到一個最小生成樹。
使用Lmax和每個猴子的最大跳躍距離比較，並計數求出所有可以達到Lmax猴子的數目。輸出該數目，即為題目答案。

完整代碼

//By Ceeji 
//Type: Prim Grpth 
//Source: HAOI2006-PM Problem 2 : Monkey 
//Date: 2009-4-5 
//States: Accepted 
Program Monkey; 
Const maxn=1000; 
      maxm=500; 
      inf='monkey.in'; 
      ouf='monkey.out'; 
Var a:array[1..maxn,1..maxn]of longint; 
    l:array[1..maxn]of longint; 
    b:array[1..maxn]of boolean; 
    xy:array[1..maxn,1..2]of longint; 
    i,j,k,n,p,ans2,m:longint; 
    min,ans:longint; 
    maxl:array[1..maxm]of longint; 
Begin 
     assign(input,inf);    reset(input); 
     assign(output,ouf);   rewrite(output); 
     fillchar(a,sizeof(a),0); 
     readln(m); 
     for i:=1 to m do 
     begin 
         read(maxl[i]); 
     end; 
     readln(n); 
     for i:=1 to n do 
     begin 
         read(xy[i,1],xy[i,2]); 
     end; 
     close(input); 
     for i:=1 to n do 
       for j:=i to n do 
       begin 
         a[i,j]:=(xy[i,1]-xy[j,1])*(xy[i,1]-xy[j,1])+(xy[i,2]-xy[j,2])*(xy[i,2]-xy[j,2]); 
         a[j,i]:=a[i,j]; 
       end; 
     for i:=1 to n do 
       l[i]:=200000000; 
     fillchar(b,sizeof(b),0); 
     l[1]:=0; ans:=0; 
     for j:=1 to n-1 do 
     begin 
          min:=200000000; 
          for i:=1 to n do 
          begin 
               if (b[i]=false)and(l[i]\=200000000 then break; 
          b[p]:=true; 
          l[p]:=0; 
          if min>ans then ans:=min; 
          for i:=1 to n do 
               if (b[i]=false)and(a[p,i]p) then l[i]:=a[p,i]; 
     end; 
     ans2:=0; 
     for i:=1 to m do 
         if (maxl[i])*(maxl[i])>=ans then inc(ans2); 
     writeln(ans2); 
     close(output); 
End.