50pts WA求助
查看原帖
50pts WA求助
229919
一E孤行楼主2021/7/7 14:47
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
using namespace std;
#define maxm 20000
#define maxn 2000
struct aaa{
    int to,from;
    double w;
}a[maxm];
struct bbb{
    double x,y;
}b[maxm];
int tot,fa[maxn],n,m;

double dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void add(int x,int y,double w)
{
    ++tot;
    a[tot].to=y;
    a[tot].from=x;
    a[tot].w=w;
}

int find(int x)
{
    if(fa[x]==x)
       return x;
    return fa[x]=find(fa[x]);
}

bool cmp(aaa x,aaa y)
{
    return x.w<y.w;
}

int main()
{
    clock_t c1=clock();
#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    //=========================================
     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;i++)
         fa[i]=i;
     for(int i=1;i<=n;i++)
     {
         double x,y;
         scanf("%lf%lf",&x,&y);
         b[i].x=x;
         b[i].y=y;
     }
     for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
           {
               double x1=b[i].x,y1=b[i].y,x2=b[j].x,y2=b[j].y;
               add(i,j,dis(x1,y1,x2,y2));
           }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y,0.0);
    }
    sort(a+1,a+1+tot,cmp);
    double sum=0.0;
    for(int i=1;i<=tot;i++)
    {
        int fx=find(a[i].from),fy=find(a[i].to);
        if(fx==fy)
           continue;
        fa[fx]=fy;
        sum+=a[i].w;
    }
    printf("%.2lf",sum);
    //=========================================
end:
    cerr<<"Tmie Used:"<<clock()-c1<<"ms"<<endl;
    return 0;
}
2021/7/7 14:47
加载中...