学步园

最小生成树的一种求法，关键还是判断两个点是否在一个回路上即并查集的运用

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
int num[210];
int pre[210];
double length;
struct edge
{
    int x, y;
    double w;
}e[9999];
void makeSet(int i)
{
    pre[i]=i;
    num[i]=0;
}
int findSet(int i)
{
    if(i!=pre[i])
        pre[i] = findSet(pre[i]);
    return pre[i];
}
void unionSet(int x, int y, double w)
{
    x = findSet(x);
    y = findSet(y);
    if(x==y) return ;
    length+=w;
    if(num[x]>num[y])
    {
        pre[y]=x;
    }
    else 
    {
        pre[x] = y;
        if(num[x]==num[y])
            num[y]++;
    }
}
bool cmp(const edge &m,const edge &n)
{
	return m.w<n.w;
}
struct Point
{
    double x,y;
}point[105];
int main()
{
    int N,T;
    cin >>T;    
    while(T--)
    {
        cin>>N;
		for(int i=1;i<=N;i++)
			cin>>point[i].x>>point[i].y;
        double t;
		int c=0;
        for(int i=1;i<=N;i++)
        {
            for(int j=i;j<=N;j++)
            {
				t= sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
                if(t<10||t>1000)
                    continue;
                else
                {
                    e[c].w=t;
                    e[c].x=i;
                    e[c++].y=j;
                }
            }
        }
        for(int i=0;i<=N;i++)
            makeSet(i);
        sort(e,e+c,cmp);
        length= 0;
        for(int i=0;i<c;i++)
        {
            int x=findSet(e[i].x);
            int y=findSet(e[i].y);
            if(x!=y)
                unionSet(x, y, e[i].w);
        }
        if(length>0)
		{
            length*= 100;
            printf("%.1lf\n",length);
        }
        else
			printf("oh!\n");
    }
}