求助,40分不知道哪里错了
查看原帖
求助,40分不知道哪里错了
477737
quyy06楼主2021/8/13 10:05
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1000005;
int mn,n,m,fa[N],cnt,ans,h[N];
double num;
struct node{
    int u,v;
    double w;
}a[10000005];
struct point{
    int x,y;
}po[1000005];
bool cmp(node x,node y){return x.w<y.w;}
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void kruskal(){
    for(int i=1;i<=mn;i++){
        int un=find(a[i].u),vn=find(a[i].v);
        if(un==vn) continue;
        fa[vn]=un;
        num=max(num,a[i].w);
        ++cnt;
        if(cnt==n-1) return;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        fa[i]=i;
        scanf("%d%d",&po[i].x,&po[i].y);
    }
    for(int i=1;i<=m;i++)
        for(int j=i+1;j<=m;j++){
            a[++mn].u=i;
            a[mn].v=j;
            a[mn].w=sqrt(pow((po[i].x-po[j].x),2)+pow((po[i].y-po[j].y),2));
        }
    sort(a+1,a+1+mn,cmp);
    //for(int i=1;i<=mn;i++) printf("%d %d %.2lf\n",a[i].u,a[i].v,a[i].w);
    kruskal();
    for(int i=1;i<=n;i++) if(h[i]>=num) ans++;
    printf("%d\n",ans);
    return 0;
}
2021/8/13 10:05
加载中...