Hihocoder \ # 1098: 최소 생 성 트 리 2 · Kruskal 알고리즘 (* 【 템 플 릿 】)

\ # 1098: 최소 생 성 트 리 2 · Kruscal 알고리즘
시간 제한:
10000ms
단일 시간:
1000ms
메모리 제한:
256MB
묘사 하 다.
작은 하 이 가 도시 의 수량 이 증가 함 에 따라 그 사이 에 사용 되 는 Prim 알고리즘 은 더 이상 사용 할 수 없 게 되 었 습 니 다. 그러나 다행히도 컴퓨터 의 분석 을 통 해 작은 하 이 는 도 로 를 건설 하기에 비교적 적합 한 노선 을 선 택 했 습 니 다. 이 수량 은 특별히 크 지 않 습 니 다.
그래서 문 제 는 '샤 오 하 이' 가 현재 N 개의 도 시 를 가지 고 있 고 그 중의 일부 도시 간 에 도 로 를 건설 하 는 비용 을 알 고 있다. 샤 오 하 이 는 최소 비용 을 들 이면 두 도시 가 모두 건설 한 도 로 를 통 해 서로 도착 할 수 있다 는 것 을 알 고 싶 어 한다.(A, B, C 세 도시 가 있다 고 가정 하면 AB 사이 와 BC 사이 에 도 로 를 건설 하면 AC 사이 도 이 두 도 로 를 통 해 연 결 될 수 있다.)
알림: 쌓 인 장점 은 언제든지 자신의 지식 창고 에서 원 하 는 것 을 추출 할 수 있다 는 것 이다!
입력
모든 테스트 포인트 (파일 입력) 가 있 고 테스트 데이터 만 있 습 니 다.
테스트 데이터 그룹 에서:
제1 행위 2 개 정수 N, M 은 소 하 이 가 가 진 도시 수 와 소 하 이 가 노선 을 선별 한 조 수 를 나타 낸다.
다음 M 줄 은 각 줄 마다 하나의 노선 을 묘사 하 는데 그 중에서 i 행 위 는 3 개의 정수 N1 i, N2 i, V i 로 이 노선 의 두 점 과 이 노선 에서 도 로 를 건설 하 는 비용 을 나타 낸다.
100% 의 데이터 에 대해 N < = 10 ^ 5, M < = 10 ^ 6 을 만족 시 키 고 임의의 i 만족 1 < = N1 i, N2 i < = N, N1 i ≠ N2 i, 1 < = V i < = 10 ^ 3.
100% 의 데 이 터 를 만족 시 키 려 면 반드시 하나의 방안 이 존재 하여 임의의 두 도시 가 서로 도착 할 수 있 도록 해 야 한다.
출력
각 조 의 테스트 데이터 에 대해 1 개의 정수 Ans 를 출력 하 는 것 은 임의의 두 도시 가 건 설 된 도 로 를 통 해 서로 최소한 필요 한 건설 비용 에 도달 할 수 있 도록 하 는 것 을 의미한다.
샘플 입력
5 29

1 2 674

2 3 249

3 4 672

4 5 933

1 2 788

3 4 147

2 4 504

3 4 38

1 3 65

3 5 6

1 5 865

1 3 590

1 4 682

2 4 227

2 4 636

1 4 312

1 3 143

2 5 158

2 3 516

3 5 102

1 5 605

1 4 99

4 5 224

2 4 198

3 5 894

1 5 845

3 4 7

2 4 14

1 4 185

샘플 출력
92

: 10 , 100


#include <stdio.h>

#include <string>

#include <iostream>

#include <string>

#include <algorithm>



using namespace std;

struct node

{

    int u;

    int v;

    int w;

    bool operator <(const node &x)const

    {

        return w<x.w;

    }

}q[1000002];

int e=0;



int fa[100002];

int findset(int x)

{

    return fa[x]!=x?fa[x]=findset(fa[x]):x;

}



int main()

{

    int n, m;

    scanf("%d %d", &n, &m);

    int i, j;

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

    {

        scanf("%d %d %d", &q[i].u, &q[i].v, &q[i].w );

    }

    sort(q, q+m);

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

    {

        fa[i]=i; //

    }

    int ans=0;

    int cnt=0;

    for(int k=0; k<m; k++)

    {

        if( findset(q[k].u)!=findset(q[k].v) )

        {

            fa[fa[q[k].u]] = fa[ q[k].v];

            ans+=q[k].w;

            cnt++;

            if(cnt==n-1)

            {

                break;

            }

        }

    }

    printf("%d
", ans ); return 0; }

좋은 웹페이지 즐겨찾기