hdu1875（最小生成树prime）

思路：一开始想用贪心来着，发现贪心有缺陷，然后就用了最小生成树来写，这里用了prime算法，首先，先建个图，两点之间的边的权值就是两个点的距离，然后直接prime模板

代码

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

#include<cstdio>

const int inf=0x7fffffff;

using namespace std;

struct node

{

    double x;

    double y;

}a[];

int n;

double Map[][];

double dist[];

bool visit[];

int flag;

double prime(int x)

{

    memset(visit,,sizeof(visit));

    flag=;

    int temp=inf;

    double lowcast;

    double sum=;

    for(int i=;i<=n;i++)

        dist[i]=Map[x][i];

    visit[x]=;

    for(int i=;i<=n-;i++)

    {

        lowcast=inf;

        for(int j=;j<=n;j++)

        {

            if(visit[j]==&&dist[j]<lowcast)

            {

                temp=j;lowcast=dist[j];

            }

        }

        if(temp==inf)

        {

            flag=;break;

        }

        visit[temp]=;

        sum+=lowcast;

        if(dist[temp]>)

            flag=;

        for(int k=;k<=n;k++)

        {

            if(visit[k]==&&dist[k]>Map[temp][k])

                dist[k]=Map[temp][k];

        }

    }

    return sum;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++)

            scanf("%lf%lf",&a[i].x,&a[i].y);

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=n;j++)

            {

                if(i==j)

                    Map[i][j]=;

                else

                    Map[i][j]=inf;

            }

        }

        for(int i=;i<=n;i++)

        {

            for(int j=i+;j<=n;j++)

            {

                Map[i][j]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));

                Map[j][i]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));

                if(Map[i][j]>||Map[i][j]<)

                {

                    Map[i][j]=inf;

                    Map[j][i]=inf;

                }

            }

        }

        double x=prime();

        if(flag==||x>=inf)

            printf("oh!\n");

        else

            {

                x=x*;

                printf("%.1lf\n",x);

            }

    }

    return ;

}