[BOJ] 백준 2463 비용

출처: https://www.acmicpc.net/problem/2463

Approach

Disjoint-Set & Union-Find  

Disjoint-Set & Union-Find

---

#include <stdio.h>
typedef long long LL;
const int MOD = (int)1e9;
const int LM = 100005;
int N, M;
int group[LM];
int urr[LM], vrr[LM];
LL sum, ans, cnt[LM];

int find(int k) {
    if (group[k] == k) return k;
    return group[k] = find(group[k]);
}

int main() {
    // freopen("input.txt", "r", stdin);

    scanf("%d %d", &N, &M);
    int i, u, v, w;
    for (i = 1; i <= N; ++i) {
        group[i] = i;
        cnt[i] = 1;
    }
    for (i = 0; i < M; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        urr[w] = u, vrr[w] = v;
        sum += w;
    }
    sum %= MOD;

    for (i = LM - 5; i > 0; --i) {
        if (urr[i]) {
            u = find(urr[i]), v = find(vrr[i]);
            if (u != v) {
                ans = (ans + sum * cnt[u] * cnt[v]) % MOD;
                group[v] = u;
                cnt[u] += cnt[v];
            }
            sum = (sum - i + MOD) % MOD;
        }
    }

    printf("%lld\n", ans);
}