40分WA蒟蒻救助
查看原帖
40分WA蒟蒻救助
528917
ma_niu_bi楼主2022/6/17 16:09
#include<cstdio>
#include<cmath>
#include<algorithm>
inline double juli(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline double max(double a,double b){
    return a>b?a:b;
}
int father[1000001];
inline int find(int i){
    if(father[i]==i)return i;
    else return father[i]=find(father[i]);
}
struct zhan{
    double x,y;
}a[1000001];
struct edge{
    int u,v;
    double w;
}b[1000001];
bool cmp1(edge a,edge b){
    return a.w>b.w;
}
bool cmp2(edge a,edge b){
    return a.w<b.w;
}
int main(){
    int s,p;
    scanf("%d%d",&s,&p);
    for(int i=1;i<=p;i++){
        father[i]=i;
    }
    for(int i=1;i<=p;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    int cnt=0;
    for(int i=1;i<=p;i++){
        for(int j=1;j<=p;j++){
            if(i!=j){
                b[++cnt]=edge{i,j,juli(a[i].x,a[i].y,a[j].x,a[j].y)};
                b[++cnt]=edge{j,i,juli(a[i].x,a[i].y,a[j].x,a[j].y)};
            }
        }
    }
    std::sort(b+1,b+cnt+1,cmp2);
    for(int i=cnt,j=0;j<s;i--){
        int fu=find(b[i].u);
        int fv=find(b[i].v);
        if(fu!=fv){
            // printf("%d %d\n",b[i].u,b[i].v);
            j+=2;
            father[fu]=father[fv];
            for(int k=i;k<=cnt;k++){
                b[k]=b[k+1];
            }
            cnt--;
        }
    }
    // puts("");
    std::sort(b+1,b+cnt+1,cmp2);
    double ans=0;
    for(int i=1;i<=cnt;i++){
        int fu=find(b[i].u);
        int fv=find(b[i].v);
        if(fu!=fv){
            // printf("%d %d %.2lf\n",b[i].u,b[i].v,b[i].w);
            father[fu]=father[fv];
            ans=max(ans,b[i].w);
        }
    }
    printf("%.2lf",ans);
    return 0;
}
2022/6/17 16:09
加载中...