백준 2463 : 비용

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

쉽지 않은 문제였다...

단 이 과정에서 해당 노드가 속해있는 최상단 뿌리노드 외에 배열을 하나 더 설정해주어야 하는데 그 뿌리노드에 속한 노드들의 개수를

저장해주어야 한다.

만약 vRoot[] 가 1,2,3,4,5,6 이면 임의로 groupSize[] 의 변수를 만들고 각 노드그룹이 속한 개수 1,1,1,1,1,1 로 초기화 시켜준다.

3과 6이 합병되면 3,6의 vRoot는 3으로 통일이 된다. 그럼 이때 3번노드는 3과 6 두개의 노드를 가지고 잇는 뿌리노드이므로 groupSize[3] = 2가 되어야한다 이는 본래 groupSize[3] 의 값인 1에다가 6의 뿌리노드(6 자신)의 개수 groupSize[6]의 값 1을 합친 2가 되는 것이다.

만약 12가 연결되어있고 36이 연결되어 있는상태면 vRoot[] 는 1 1 3 4 5 3 이다.(1,2의 뿌리노드는 1 이고 3,6의 뿌리노드는 3이다.)

또한 groupSize[1] 의 값은 2이고 groupSize[3] 의 값도 2이다. (각각 노드를 2개씩 가지고 있는 그룹임)

이때 2와 6을 연결한다면 vRoot[] 는 1 1 1 4 5 1 처럼 1234노드의 뿌리노드는 모두 1이된다.

따라서 groupSize[1] 의 값은 4가 된다 (groupSize[1] += groupSize[3] 의 연산결과)

비용이 작은 다리부터 제거한다는 내용을 비용이 비싼 다리부터 건설한다는 역발상을 기본으로 하는데

세부적인 사항(cycle이 있는 상태여도 무조건 건설하는 것이므로 비용은 소모한다는 것, 그룹의 사이즈를 새로운 배열에 저장시켜 갱신시켜나가는것)의 구현이 까다로운 문제였다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include <iostream> #include <vector> #include <algorithm> #define MAX 100001 #define MOD 1000000000 using namespace std; int n, m; long long tCost = 0; long long ret = 0; class Edge{ public: int i, j ,w; Edge(int i, int j, int w):i(i),j(j),w(w){} bool operator < (const Edge &e) const { return w > e.w; } }; vector<Edge> edges; int vRoot[MAX] = {0, }; long long groupSize[MAX] = {0, }; int findRoot(int v){ if(vRoot[v] == v) return v; return vRoot[v] = findRoot(vRoot[v]); } void reverseKruskal(){ for(int i = 1; i <= n; i++){ vRoot[i] = i; groupSize[i] = 1; } sort(edges.begin(), edges.end()); for(Edge e : edges){ int rootI = findRoot(e.i); int rootJ = findRoot(e.j); if(rootI != rootJ){ ret += groupSize[rootI] * groupSize[rootJ] * tCost; ret %= MOD; vRoot[rootJ] = rootI; groupSize[rootI] += groupSize[rootJ]; } tCost -= e.w; } cout << ret << endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; while(m--){ int x, y, w; cin >> x >> y >> w; edges.push_back(Edge(x, y, w)); tCost += w; } reverseKruskal(); return 0; }