[BOJ] 2463 - 비용

[백준] 2463 - 비용

풀이

문제를 읽자 마자 생각난 것은 바로 MST였다.
간선의 총 합을 구해두고, MST를 만들면서 연결하는 간선을 총합에서 빼고, 연결되는 두 연결그래프가 서로 연결되는 경우의 수만큼 그 합을 곱하여 MOD연산한 값을 더하면서 값을 구하면 되지 않을까?
그런데 계산을 해보니 이상한 값이 나왔다. 문제를 잘못 이해한 것 같다.
그래서 이런 저런 고민을 했는데… 문제를 푼 지 워낙 오래되어 기억은 잘 나지 않고..
어쨌든 결론을 말하자면 위의 방법대로 MST를 만드는 것은 같지만, PQ를 최대힙으로 바꾸어 만들면 되는 것이었다.
기존 MST아이디어에 살짝의 변형을 하면 된달까..

소스코드

#include <bits/stdc++.h>
#define MOD 1000000000
using namespace std;
typedef tuple<int, int, int> T;
typedef long long ll;

priority_queue<T> pq;
ll parent[100005], cnt[100005];

ll find(ll x) {
    if (parent[x] == 0) return x;
    return parent[x] = find(parent[x]);
}

void merge(ll x, ll y) {
    if (find(x) == find(y)) return;
    cnt[find(y)] += cnt[find(x)];
    parent[find(x)] = find(y);
    find(x);
}

int main(void) {
    ll sum = 0, ans = 0, n, m;
    scanf("%lld %lld", &n, &m);
    fill(cnt, cnt + n + 1, 1);
    for (ll i = 0; i < m; i++) {
        ll x, y, w;
        scanf("%lld %lld %lld", &x, &y, &w);
        pq.push({ w, x, y });
        sum += w;
    }
    
    while (!pq.empty()) {
        ll x = get<1>(pq.top()), y = get<2>(pq.top()), w = get<0>(pq.top());
        pq.pop();
        if (find(x) != find(y)) {
            ans = (ans + (((cnt[find(x)] * cnt[find(y)]) % MOD) * sum) % MOD) % MOD;
            merge(x, y);
        }
        sum -= w;
    }

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