도시 분할 계획

백준 1647번: 도시 분할 계획

아이디어

트리가 만들어지면 간선이 총 N-1개이다. MST를 만들다 간선의 개수가 N-2가 되었을 때 멈춘다면 도시가 최소의 비용으로 분할된다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 100001;
int N, M;
int p[MAX];

int find(int n) {
    if (p[n] < 0) return n;
    return p[n] = find(p[n]);
}

void merge(int n1, int n2) {
    n1 = find(n1);
    n2 = find(n2);
    if (n1 == n2) return;
    p[n1] += p[n2];
    p[n2] = n1;   
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    vector<pair<int, pair<int, int>>> v;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({c, {a, b}});
    }
    sort(v.begin(), v.end());
    memset(p, -1, sizeof(p));
    int cnt = 0, ans = 0;
    for (auto p : v) {
        int c = p.first;
        int a = p.second.first;
        int b = p.second.second;
        if (find(a) == find(b)) continue;
        ans += c;
        cnt++;
        merge(a, b);
        if (cnt == N-2) break; 
    }
    cout << ans << '\n';

    return 0;
}

여담

즐거운 MST