[백준] 2463: 비용

0. 문제 주소

 

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

2463번: 비용

 

 

1. 풀이

 

Cost(u, v)의 정의를 보자.

 

Cost(u,v)는 다음에서 제거되는 간선들의 가중치 합이다: u와 v사이의 경로가 있으면 이 그래프의 최소 가중치 간선을 그래프에서 제거한다. 이 과정을 u와 v사이의 경로가 없을 때까지 반복한다.

 

 

Cost를 구하기 위해 생각해봐야 할 점은, "u와 v 사이의 경로가 없을 때까지 반복한다"는 점이다.

 

u와 v 사이의 경로 간선 중, 매번 최소 가중치를 가지는 간선을 제거하기 때문에 이 과정을 역으로 생각해 볼 것이다.

 

크루스칼 알고리즘과 유사하지만, 최대 가중치를 가지는 간선부터 그래프에 포함시킨다.

 

이 때 u와 v가 기존엔 연결되어 있지 않다가, 이번 간선으로 하여금 연결 되었다면, u와 v 사이의 경로가 생긴 것이다.

 

여기서, 앞으로 남은 간선들의 가중치 + 이번에 추가한 간선의 가중치 = Cost(u, v)로 계산할 수 있음을 알 수 있다.

 

한 가지 더 고려해야 할 점이 있다.

 

 

 

(2, 3) 간선이 새로 들어오며 구할 수 있는 cost 값은 Cost(2, 3) 뿐이 아니다.

정확히는 Cost(1, 3), Cost(2, 3), Cost(1, 4), Cost(2, 4) 총 4개의 값이다.

 

이는 2가 포함된 집합에서 원소 하나, 3이 포함된 집합에서 원소 하나를 골라 만들 수 있는 순서쌍의 개수와 같다.

이는 두 집합의 원소의 개수를 곱함으로써 얻을 수 있다.

 

구하고자 하는 것은, "u<v인 모든 두 정점 u,v에 대한 Cost(u,v)들의 총 합"이기 때문에, 순서를 고려하지 않고 한 번씩만 세어주며 값들의 합을 저장하면 된다.

 

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define MAX 100005
#define ll long long
#define pii pair<int, ll>
#define piii pair<ll, pair<int, int>>
#define MOD 1000000000LL

using namespace std;

int N, M;
int p[MAX];
int family[MAX];
vector<pii> graph[MAX];
priority_queue<piii> PQ;

int find(int node){
    if (p[node] < 0) return node;
    
    return p[node] = find(p[node]);
}

bool merge(int a, int b){
    int roota = find(a);
    int rootb = find(b);
    
    if (roota == rootb) return false;
    
    p[rootb] += p[roota];
    p[roota] = rootb;
    return true;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d %d", &N, &M);
    memset(p, -1, sizeof(p));
    fill(family+1, family+N+1, 1);
    
    ll total_edge = 0LL;
    ll ans = 0LL;
    for (int i=0;i<M;i++){
        int u, v;
        ll w;
        scanf("%d %d %lld", &u, &v, &w);
        graph[u].push_back(pii(v, w));
        graph[v].push_back(pii(u, w));
        PQ.push(make_pair(w, pii(u, v)));
        total_edge += w;
    }
    
    while(!PQ.empty()){
        auto pp = PQ.top();
        PQ.pop();
        ll weight = pp.first;
        int u = pp.second.first, v = pp.second.second;
        if (find(u) != find(v)){
            ans += ( ( ((ll)p[find(u)] * (ll)p[find(v)] ) % MOD ) * total_edge) % MOD;
            merge(u, v);
        }
        total_edge -= weight;
    }
    printf("%lld\n", ans % MOD);    
    
    return 0;
}