BOJ)1647 도시 분할 계획

문제: icpc.me/1647

최소 스패닝 트리를 구해주면 된다.

주의할 점은 하나인 마을을 두개로 나누고 싶다고 하고 있기 때문에 N-2개의 간선만 연결해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int, pair<int, int>>> vt;
int n, m, a, b, c, r;
int par[100010];
int find(int x) {
    if (par[x] == x)return x;
    return par[x] = find(par[x]);
}
void merge(int x, int y,int z) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    par[x] = y;
    r += z;
    n--;
}
int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        par[i] = i;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        vt.push_back({ c,{a,b} });
    }
    sort(vt.begin(), vt.end());
    for (auto it : vt) {
        if (n == 2)break;
        int x = it.second.first;
        int y = it.second.second;
        int z = it.first;
        merge(x, y, z);
    }
    printf("%d\n", r);
    return 0;
}