[백준] 1922번 네트워크 연결

[적용한 알고리즘]

MST(최소 신장 트리, 미니멈 스패닝 트리, 최소 스패닝 트리..)

 

[아이디어]

기본 문제라고 한다. 항상 그렇듯 출처는 kks 님의 블로그

 

[교훈]

Edge 를 정의한 방식이 싱기방기하다.

공부를 더해야겠다.

 

<코드>

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

int UF[1001];

int find(int a){
    if (UF[a] < 0) return a;
    return UF[a] = find(UF[a]);
}

bool merge(int a, int b){
    a = find(a);
    b = find(b);

    if (a == b) return false;
    UF[b] = a;
    return true;
}

struct Edge{
    int u, v, w;
    Edge(): Edge(-1, -1, 0){}
    Edge(int u1, int v1, int w1): u(u1), v(v1), w(w1){}
    bool operator < (const Edge& O) const {
        return w < O.w;
    }
};
int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    Edge e[100001];

    for (int i = 0; i < M; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        e[i] = Edge(a - 1, b - 1, c);
    }
    sort(e, e + M);

    int result = 0;
    int cnt = 0;
    fill(UF, UF + N, -1);
    for (int i = 0;; i++){
        if (merge(e[i].u, e[i].v)){
            result += e[i].w;
            if (++cnt == N - 1) break;
        }
    }

    printf("%d\n", result);
    return 0;
}