HDU 1875（最小生成树）

因为是全连接图，所以也可以用最小生成树

这道题给边加了一个限制条件，(10<=x<=1000),所以可能不能全连通，需要判断

#include <cstdio>

#include <iostream>

#include <queue>

#include <cmath>

using namespace std;

#define sf scanf

#define pf printf

#define debug printf("!\n")

#define blank printf("\n")

#define mem(a,b) memset(a,b,sizeof(a))

const int MaxN = ;

const int INF = <<;

int p[MaxN];

int r[MaxN*MaxN],u[MaxN*MaxN],v[MaxN*MaxN];

double w[MaxN*MaxN];

int m,n,vex;

struct point

{

    int x,y;

};

point pt[];

int find(int x){return p[x]==x?x:p[x]=find(p[x]);}

int cmp(const int a,const int b)

{

    return w[a]<w[b];

}

double kruskal()

{

    double ans = ;

    int i;

    for(i = ;i<n;i++) p[i] = i;

    for(i = ;i<m;i++) r[i] = i;

    sort(r,r+m,cmp);

    for(i = ;i<m;i++)

    {

        int e = r[i];

        int x = find(u[e]);

        int y = find(v[e]);

        if(x!=y)

        {

            ans+=w[e];

            p[x] = y;

            vex++;

        }

    }

    return ans;

}

double getD(point p1 ,point p2)

{

    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));

}

int main()

{

    int i,j,t;

    sf("%d",&t);

    while(t--)

    {

        mem(u,);

        mem(v,);

        mem(w,);

        m=;

        vex = ;

        sf("%d",&n);

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

        {

            sf("%d%d",&pt[i].x,&pt[i].y);

        }

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

        {

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

            {

                double d = getD(pt[i],pt[j]);

                if(d< || d>)

                {

                    continue;

                }

                u[m] = i;

                v[m] = j;

                w[m++] = d;

            }

        }

        double ans = kruskal();

        if(vex<n)

            pf("oh!\n");

        else

            pf("%.1lf\n",ans*);

    }

    return ;

}