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.

本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。