HDU 1875 원활 한 프로젝트 재 접속 (최소 생 성 트 리)

원활 한 공사 재 개
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 22821 Accepted Submission(s): 7288
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) - 전진 시 뮬 레이 션
이 문 제 는 최소 생 성 트 리 문제 로 어렵 지 않다.다만 Kruskal 을 사용 할 때 아래 의 가중치 크기 를 판단 하고 좌 표를 점 으로 바 꿀 때 초학 자 에 게 조금 어 려 울 수 있 습 니 다.다음은 AC 코드 입 니 다.

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

struct node
{
    int u,v;
    double cost;
}e[10005];

int pre[105];
int fin(int x)
{
    if(x==pre[x]){return x;}
    else
    {
        pre[x]=fin(pre[x]);
        return pre[x];
    }
}

void join(int x,int y)
{
    int t1=fin(x);
    int t2=fin(y);
    if(t1!=t2)
    {
        pre[t1]=t2;
    }
}
double a[105];
double b[105];

bool cmp(node x,node y)
{
    return x.cost<y.cost;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lf %lf",&a[i],&b[i]);
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                e[cnt].u=i;
                e[cnt].v=j;
                e[cnt].cost=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));
                cnt++;
            }
        }
        for(int i=0;i<=n;i++)
        {
            pre[i]=i;
        }
        sort(e,e+cnt,cmp);
        double sum=0;
        int sum1=0;
        for(int i=0;i<cnt;i++)
        {
            if(fin(e[i].u)!=fin(e[i].v)&&e[i].cost>=10.0&&e[i].cost<=1000.0)
            {
                sum1++;
                join(e[i].u,e[i].v);
                sum+=e[i].cost*100;
            }
        }
        if(sum1==n-1)
        {
            printf("%.1lf
",sum);
        }
        else
        {
            printf("oh!
");
        }
    }
    return 0;
}