HDU 1875 는 최소 생 성 트 리 입 니 다.

원활 한 공사 재 개 Time Limit: 2000 / 1000 MS (Java / Others) Memory Limit: 32768 / 32768 K (Java / Others) Total Submission (s): 5242 Accepted Submission (s): 1535 Problem 설명 은 모두 가 '백도 호' 라 는 곳 을 들 었 을 것 이 라 고 믿 습 니 다. 백도 호 주민 들 은 서로 다른 작은 섬 에 살 고 있 습 니 다. 그들 이 다른 작은 섬 에 가 고 싶 을 때 작은 배 를 저어 이 루어 져 야 합 니 다.현재 정 부 는 백도 호 를 대대적으로 발전 시 키 기로 결정 했다. 발전 에 있어 서 먼저 해결 해 야 할 문 제 는 당연히 교통 문제 이다. 정 부 는 백도 호의 원활 한 소통 을 실현 하기 로 결정 했다!탐사 팀 RPRush 를 통 해 백도 호의 상황 을 충분히 파악 한 뒤 조건 에 맞 는 작은 섬 사이 에 다 리 를 놓 기로 했다. 조건 에 맞 는 다 는 것 은 작은 섬 2 곳 사이 의 거리 가 10m 보다 작 으 면 안 되 고 1000 m 이상 이면 안 된다 는 것 이다.물론 돈 을 아 끼 기 위해 서 는 임 의 2 개 작은 섬 사이 에 길이 있 으 면 된다.그 중 다리 의 가격 은 미터 당 100 위안 이다.Input 입력 은 여러 그룹의 데 이 터 를 포함한다.입력 은 먼저 정수 T (T < = 200) 를 포함 하고 T 조 데이터 가 있 음 을 의미 합 니 다.각 조 의 데 이 터 는 먼저 하나의 정수 C (C < = 100) 로 작은 섬의 개 수 를 대표 하고 그 다음은 C 조 좌표 로 모든 작은 섬의 좌 표를 대표 한다. 이런 좌 표 는 모두 0 < = x, y < = 1000 의 정수 이다.Output 각 조 의 입력 데이터 출력 줄 은 다 리 를 건설 하 는 최소 비용 을 대표 하고 결 과 는 작은 숫자 를 유지 합 니 다.모든 원활 한 공 사 를 이 루 지 못 하면 수출 "oh!".Sample Input2210 1020 2031 12 21000 1000 Sample Output1414.2oh!
 
이것 은 상당히 비극 적 이다. 그 거리 가 10 보다 1000 보다 작 으 면 안 되 기 때문에 N 번 을 잘못 구 했 으 니 반드시 세심 해 야 한다.  
My Source Code：  

//// HDU_1875.cpp : Defines the entry point for the console application.

#include <stdio.h>

#include <math.h>

#include <algorithm>

using namespace std;



//          

#define MaxVertexNum 105

//          

#define MaxEdgeNum 105*52+2

#define Max 0xFFFFFFF



struct edge

{

    int from;

    int end;

    double length;

};



edge edgeset[MaxEdgeNum];

double node[MaxVertexNum][2];



bool compare(const struct edge& a,const struct edge& b) 

{ 

    return a.length<b.length; 

} 

 

int Kruskal(edge e[MaxEdgeNum],edge c[MaxEdgeNum],const int& vertexs) 

{ 

    int i,j,k,d; 

    //   m1 m2                      

    int m1,m2; 

      

    int s[MaxVertexNum][MaxVertexNum]; 

    //     

    for(i=0;i<vertexs;i++) 

        for(j=0;j<vertexs;j++) 

        { 

            if(i==j) 

                s[i][j]=1; 

            else

                s[i][j]=0; 

        } 

    //          

    k=0; 

    d=0; 

  

    while(k<vertexs-1) 

    { 

        for(i=0;i<vertexs;i++) 

        { 

            if(s[i][e[d].from]==1) 

                m1=i; 

            if(s[i][e[d].end]==1) 

                m2=i; 

        } 

        if(m1!=m2) 

        { 

            c[k++]=e[d]; 

            for(j=0;j<vertexs;j++) 

            { 

                s[m1][j]=s[m1][j]||s[m2][j]; 

                s[m2][j]=0; 

            } 

        } 

        d++; 

    } 

    return k; 

} 

  



int main(int argc, char* argv[])

{

	int t,n;

	int i,j,k,r,flag;

	scanf("%d",&t);

	for(i=0;i<t;i++)

	{

		flag=1;

		scanf("%d",&n);

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

		{

			scanf("%lf%lf",&node[j][0],&node[j][1]);

		}



		k=0;

		for(j=0;j<n-1&&flag;j++)

		{

			for(r=j+1;r<n;r++)

			{

				double length=sqrt((node[j][0]-node[r][0])*

					(node[j][0]-node[r][0])+(node[j][1]-node[r][1])*

					(node[j][1]-node[r][1]));

				//      

				if(length<10||length>1000)

				{

					length=Max;

				}

				edgeset[k].from=j;

				edgeset[k].end=r;

				edgeset[k].length=length;

				k++;

			}

		}



		edge c[MaxEdgeNum];

		sort(edgeset,edgeset+k,compare);

		int edges=Kruskal(edgeset,c,n);

		double MinLength=0;

		for(j=0;j<edges;j++)

		{

			if(c[j].length==Max)

			{

				flag=0;

				printf("oh!
");

				break;

			}

			MinLength+=c[j].length;	

		}

		if(flag)

			printf("%.1lf
",MinLength*100);

	}

	return 0;

}