비용 - 2463

//2463 - 비용
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define MOD 1000000000
 
int N, M;
vector<pair<int, pair<int, int>>> edge;
vector<int> msize;
 
struct DisjointSet
{
    vector<int> parent, rank;
 
    DisjointSet(int n) : parent(n+1), rank(n+1, 1)
    {
        for(int i = 1; i<=n; ++i)
            parent[i] = i;
    }
 
    int find(int u)
    {  
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
 
    bool merge(int u, int v)
    {
        u = find(u); v = find(v);
        if(u == v) return false;
        if(rank[u] > rank[v]) swap(u, v);
        msize[v] += msize[u];
        parent[u] = v;
        if(rank[u] == rank[v]) ++rank[v];
        return true;
    }
};
 
int main()
{
    int N, M;
    cin >> N >> M;
    msize = vector<int>(N+1, 1);
    int x, y, r;
    long long ans = 0;
    long long allSum = 0;
    DisjointSet sets(N);
    edge = vector<pair<int, pair<int, int>>>(M);
    for(int i = 0; i<M; ++i)
    {
        cin >> x >> y >> r;
        allSum += r;
        edge[i].first = -r;
        edge[i].second.first = x;
        edge[i].second.second = y;
    }
    sort(edge.begin(), edge.end());
    for(int i = 0; i<M; ++i)
    {
        long long u = msize[sets.find(edge[i].second.first)];
        long long v = msize[sets.find(edge[i].second.second)];
        if(sets.merge(edge[i].second.first, edge[i].second.second))
        {
            ans += (u*v%MOD)*allSum%MOD;
            ans %= MOD;
        }
        allSum += edge[i].first;
    }
    cout << ans;
}

 

 

 

 

 

 

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

2463번: 비용

 

 

 

 

 

 

비용

UNION-FIND 문제입니다.

문제의 조건대로 하나하나 cost(u, v)를 구할수 없습니다.(시간초과)

간선을 작은것부터 하나씩 삭제하는 것이 아니라 큰 간선부터 추가를 하고,

간선이 추가될때 마다 서로 연결되어있는 정점끼리 한 집합을 이루게 하면,

집합끼리 합쳐질때 각각의 집합의 원소들은 그 순간(특정 간선이 추가되었을때) 상대 집합들의 원소들과 모두 최초로 연결되는 것이니, 이때 연결된 간선을 전체 간선 가중치의 합에서 뺀것만큼이 cost(u, v)가 되게 됩니다. (u, v는 서로 다른 집합에 속해있는 정점, 두 집합이 합쳐질때 cost(u, v)가 얼마인지 알수 있게 됩니다)

cost(u, v)는 합쳐지는 두집합의 원소의 곱만큼 생성됩니다.