hdu 1875 원활 한 공정 재 접속 (kruskal 알고리즘 계산 최소 생 성 트 리)

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

   
   
   
   

    
    
    
    2
2
10 10
20 20
3
1 1
2 2
1000 1000
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1414.2
oh!
   
   
   
   

 
Author
8600
 
Source
2008 절 대 대학원 재시험 평가 전 (2) - 전진 시 뮬 레이 션
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   1233  1232  1863  1874  1102 
최소 생 성 트 리 문제, 두 가지 알고리즘 prim 과 kruskal.여기 서 제 가 쓰 는 두 번 째 알고리즘.
처음으로 RE.배열 이 너무 작 구나...CNN!!
n 각 작은 섬 마다 의 거리 (10 보다 1000 이상 의 거리) 를 계산 하고 구조 체 eg 에 저장 합 니 다.sort 는 거리 에 따라 작은 것 부터 큰 것 까지 정렬 한 다음 에 kruskal 알고리즘 을 사용 합 니 다.
마지막 으로 뿌리 가 하나 인지 아 닌 지 를 판단 한다.
아니면 코드 가 실제로 왔 는 지 간단 한 주석 이 있 습 니 다.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
int fa[105],n;
struct node//存贮第一次输入的坐标，一定要是浮点型的
{
    double x,y;
}c[105];
struct node1//存贮两个小岛的编号和小岛的距离
{
    int a,b;
    double l;
}eg[10005];
bool cmp(node1 x,node1 y)//比较函数
{
    return x.l<y.l;
}
int find(int x)//查找根并且缩短路径
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void init()//初始化
{
    for(int i=0;i<n;i++)
    fa[i]=i;
}
int main()
{
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        scanf("%d",&n);
        init();
        memset(&c,0,sizeof(&c));
        memset(&eg,0,sizeof(&eg));
        for(int i=0;i<n;i++)
        scanf("%lf %lf",&c[i].x,&c[i].y);
        int k=0;
        for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
        {
            double temp=sqrt(pow(c[i].x-c[j].x,2)+pow(c[i].y-c[j].y,2));
            if(temp>=10&&temp<=1000)//如果距离大于等于10小于等于1000
            {
                eg[k].a=i,eg[k].b=j,eg[k].l=temp;
                k++;        
            }
        }
        sort(eg,eg+k,cmp);//根据距离排序<span style="white-space:pre">	</span>
        double sum=0;//计算最小生成树的和
        for(int i=0;i<k;i++)
        {
            int x=find(eg[i].a);
            int y=find(eg[i].b);
            if(x!=y)
            fa[x]=y,sum+=eg[i].l;
            
        }
        int count=0;
        for(int i=0;i<n;i++)//判断树根个数
        if(fa[i]==i)
        count++;
        if(count!=1)
        printf("oh!
");
        else
        printf("%.1lf
",sum*100);
    }
    return 0;
}