最小生成树 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!\n");

        else printf("%.1lf\n",sum*100.0);

    }

    return 0;

}

巴特西

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

最新文章

热门文章