题解 P2504 【[HAOI2006]聪明的猴子】

佚名 6年前 (2019-04-10) 随笔 836人围观抢沙发百度已收录

记录最小生成树的最大边然后判断每只猴子的跳跃距离是否大于最大边的权值

如果满足条件即$ans++$

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

然后输出结果即可

看了一下自己两个月前的代码 dis的返回值搞错了……

代码如下:

#include<bits/stdc++.h>
using namespace std;
int m,n,h[505],f[1005],cnt,px,py,ans;
double flag;
struct p1{
    int x,y;
}a[1005];
struct p2{
    int x,y;
    double z;
}b[1000005];
bool cmp(p2 a,p2 b){
    return a.z<b.z;
}
int find(int x){
    if (x==f[x]) return x;
    return f[x]=find(f[x]);
}
double dis(int x1,int y1,int x2,int y2){
    return sqrt(double(x1-x2)*(x1-x2)+double(y1-y2)*(y1-y2));
}
int main(){
    scanf("%d",&m);
    for (int i=1;i<=m;i++) scanf("%d",&h[i]);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++){
            cnt++;
            b[cnt].x=i;
            b[cnt].y=j;
            b[cnt].z=dis(a[i].x,a[i].y,a[j].x,a[j].y);
        }
    sort(b+1,b+cnt+1,cmp);
    for (int i=1;i<=cnt;i++){
        px=find(b[i].x);
        py=find(b[i].y);
        if (px==py) continue;
        f[px]=py;
        flag=b[i].z;
    }
    for (int i=1;i<=m;i++) 
        if (h[i]*1.0>=flag) ans++;
    printf("%d\n",ans);
    return 0;
}