[BOJ 17132] 두더지가 정보섬에 올라온 이유

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

17132번: 두더지가 정보섬에 올라온 이유

Tag : dsu

 

문제요약

트리 위의 모든 정점쌍에 대해 경로 위의 간선 중 최소 가중치를 더하는 문제다.

 

풀이

https://kim1109123.tistory.com/17 의 d번과 동일하고 너무 전형적인 dsu 문제다. 

간선을 내림차순으로 정렬한 후 차례대로 이어주면 현재 간선이 최소인 모든 정점쌍을 구할 수 있다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int N;
int sz[101010];
int pa[101010];
vector<tuple<int, int, int>> edge;

int find(int a) { return a == pa[a] ? a : (pa[a] = find(pa[a])); }

void merge(int a, int b) {
    a = find(a); b = find(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    pa[b] = a;
}

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
int z[36];
char*c=(char*)mmap(0,z[12],1,2,0,fstat(0,(struct stat *)z));
inline int f(){int x=0;bool e;c+=e=*c=='-';while(*c>='0')x=10*x+*c++-'0';c++;return e?-x:x;}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    N = f();
    for(int i=1; i<=N; i++) pa[i] = i, sz[i] = 1;
    edge.resize(N - 1);
    for(auto &[k, i, j] : edge) i = f(), j = f(), k = f();
    sort(edge.begin(), edge.end(), greater<>());
    ll ans = 0;
    for(auto &[k, i, j] : edge) {
        if(find(i) == find(j)) continue;
        ll a = sz[find(i)];
        ll b = sz[find(j)];
        merge(i, j);
        ans += k * a * b;
    }
    cout << ans << endl;
}