题解 | #[HAOI2006]聪明的猴子#

题意

求出 满足条件的猴子的数目，满足的条件是：能在这个地区的所有树冠上觅食
换成用数学语言来描述条件 ：猴子的最大跳跃距离 MaxD 需大于或等于 最小生成树 边集 中最长的那条边

最小生成树：联通该地区所有的树冠 所形成的最小生成树

思路

prim 算法扫一遍，在这个过程中，求出 最小生成树 边集中 的最大边长 ，统计 最大跳跃距离 大于或等于其的 猴子的数目

注意： double 类项 不能用memset 初始化 （ wa了好久 最后发现的 ）

综上，Code 如下 .

Code

#include <bits/stdc++.h>

using namespace std;

const int N=1010;

struct node{
    int x,y;
}p[N];  
bool st[N];
double a[N],g[N][N],dist[N]; 
int n,m;

int pf(int x){
    return x*x;
}

double prim(){
    double res=-1;

    for(int j=1;j<=n;j++)  dist[j]=1e8; // double 不能用memset 
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
        st[t]=true;
        if(i) res=max(dist[t],res);  // 求最长边
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}

int main(){
    cin>>m;
    for(int i=1;i<=m;i++) cin>>a[i];

    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
        int x=p[i].x,y=p[i].y,x1=p[j].x,y1=p[j].y;
        g[j][i]=g[i][j]=sqrt(pf(x-x1)+pf(y-y1));    
    }

    double t=prim();
    int res=0;
    for(int i=1;i<=m;i++) if(a[i]>=t) res++;    
    cout<<res<<endl;

    return 0;
}