10423번: 전기가 부족해

https://www.acmicpc.net/problem/10423


$O(m\lg n+k)$

모든 발전소가 하나의 집합에 있다고 가정하고 최소신장트리를 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, k, p[1001], r;
struct st {
    int x, y, z;
}e[100000];
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0, t; i < k; i++) scanf("%d", &t), p[t] = 0;
    for (int i = 0; i < m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
    sort(e, e + m, [](st i, st j) {return i.z < j.z; });
    for (int i = 0; i < m; i++) {
        int ra = f(e[i].x), rb = f(e[i].y);
        if (ra^rb) p[ra] = rb, r += e[i].z;
    }
    printf("%d", r);
    return 0;
}