[백준] 1647번 도시 분할 계획

[적용한 알고리즘]

MST(크루스칼)

 

[아이디어]

하고 싶은게 두 가지다.

1. 두 마을로 쪼개고 싶다. (최소한의 경로만 남겨놓고)

2. 유지비를 최소로 하고 싶다. 

 

MST 를 만들어야할 것 같은데, 두 마을로 어떻게 쪼갤 지 고민을 하다보면,

우선 MST 를 만든 뒤, 만든 간선 중 가장 값이 큰 간선 하나를 제외시켜버리면 된다.

 

근데 크루스칼 알고리즘에서는 값이 가장 큰 간선이 가장 마지막에 추가되므로,

마지막 반복문을 안돌리면 되는 거다.

 

[교훈]

그래프..

 

<코드>

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

struct Edge {
    int start, end, cost;
    bool operator < (const Edge &other) const {
        return cost < other.cost;
    }
};

int Parent[100001];

int Find(int x){
    if (x == Parent[x]){
        return x;
    }
    return Parent[x] = Find(Parent[x]);
}

bool Merge(int x, int y){
    x = Find(x);
    y = Find(y);

    if (x == y) return false;
    Parent[x] = y;
    return true;
}

int main(){
    int N, M;
    scanf("%d %d", &N, &M);

    for (int i = 1; i <= N; i++){
        Parent[i] = i;
    }

    vector<Edge> E;
    for (int i = 0; i < M; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        E.push_back({from, to, cost});
    }

    sort(E.begin(), E.end());
    int ans = 0;
    int cnt = 0;

    for (int i = 0; i < M; i++){
        Edge cur = E[i];

        if (Merge(cur.start, cur.end)){
            ans += cur.cost;
            cnt++;
        }

        if (cnt == N - 2){
            break;
        }
    }

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