最小生成树 kuangbin专题最后一个题

题目链接：https://cn.vjudge.net/contest/66965#problem/N

注释：这道题需要用krustra,用prim的话可能会超时。并且在计算距离的时候要尽量减少步骤，具体注意事项在代码中说吧。

AC代码：

#include<iostream>
#include<string>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
# define inf 0x3f3f3f3f
# define maxn 5000
int father[maxn];
struct Point
{
    int x,y;
} q[maxn];
struct Edge
{
    int fr;
    int to;
    double cost;
} edge[maxn];
double cal(int t1,int t2)
{
    double s1=(q[t1].x-q[t2].x);
    double s2=(q[t1].y-q[t2].y);
    return (s1*s1+s2*s2);//不要直接计算sqrt，在累积和的时候计算
}
bool cmp(Edge t1,Edge t2)
{
    return t1.cost<t2.cost;
}
int Find(int t)
{
    return t==father[t]? t:father[t]=Find(father[t]);
}
int main()
{
    int T;
   scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&q[i].x,&q[i].y);
            father[i]=i;
        }
        int num=0;
        for(int i=1; i<=n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                double temp=cal(i,j);
                if(temp<100.0||temp>1000000.0)continue;
                    edge[++num].fr=i;
                    edge[num].to=j;
                    edge[num].cost=temp;
            }
        }
       // cout<<num<<endl;
        sort(edge+1,edge+num+1,cmp);
        double sum=0;
        int ans=0;
        for(int i=1; i<=num; i++)
        {
            int t1=Find(edge[i].fr);
            int t2=Find(edge[i].to);
            if(t1!=t2)
            {
                father[t1]=t2;
                sum+=sqrt(edge[i].cost);
                ans++;
            }
            if(ans==n-1)break;
        }
        if(ans<n-1)printf("oh!
");
        else printf("%.1lf
",sum*100.0);
    }
    return 0;
}