백준 10423 : 전기가 부족해

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

Union-Find를 살짝 응용한 문제.

최소 스패닝 트리이되 무조건 모든 노드가 연결이 되는 문제가 아니다.

모든 도시가 연결되어있을 필요는 없고 다만 모든 도시가 발전소와 연결되어 있기만 하면 된다.

발전소를 보유하고 있는 도시 가 주어지므로 발전소를 -1로 두었다.

뿌리노드 배열을 -1로 두고 최종적으로 모든 노드의 뿌리노드가 -1이 되면 발전소와 연결이 된 것이다.

예시를 참고하자면 1,2,9번 도시가 발전소를 보유하고 있으므로 다음과 같이 설정하고 시작해준다.

 * vRoot[]

[1,2,3,4,5,6,7,8,9]

-> [-1,-1,3,4,5,6,7,8,-1]

 ... -> [-1,-1,-1,-1,-1,-1,-1,-1,-1] 이 되면 연결완료.

Union-Find를 조금만 수정하면 된다.

우선 각 노드가 최종적으로 도달하여야 할 뿌리노드는 -1 이므로 기존 find하는 과정에서

if(vRoot[v] == -1){

return -1;

}

을 상단에 넣어주면 된다.

또한 합병 과정에서도 무작정 한쪽 뿌리노드의 부모를 다른쪽 뿌리노드로 설정해주면 안된다.

-1이 최상단 뿌리노드여야 하므로 만약 연결하려는 두 노드의 한쪽 뿌리노드가 -1 이라면

반대쪽 뿌리노드의 부모를 -1로 지정해주어야 한다.

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 61 62 63 64

#include <iostream> #include <vector> #include <algorithm> #define MAX 1001 using namespace std; int n, m, k, cost = 0; int vRoot[MAX] = {0, }; class Tunnel{ public: int i, j, w; Tunnel(int i = 0, int j = 0, int w = 0) :i(i), j(j), w(w) {} bool operator < (const Tunnel &t) const { return w < t.w; } }; vector<Tunnel> tunnel; int findRoot(int v){ if(vRoot[v] == -1) return -1; else if(vRoot[v] == v) return v; return vRoot[v] = findRoot(vRoot[v]); } void kruskal(){ sort(tunnel.begin(), tunnel.end()); for(Tunnel t : tunnel){ int rootI = findRoot(t.i); int rootJ = findRoot(t.j); if(rootI != rootJ){ if(rootI == -1){ vRoot[rootJ] = rootI; }else if(rootJ == -1){ vRoot[rootI] = rootJ; }else{ vRoot[rootJ] = rootI; } cost += t.w; } } cout << cost << endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> k; for(int i = 1; i <= n; i++){ vRoot[i] = i; } while(k--){ int tp; cin >> tp; vRoot[tp] = -1; } while(m--){ int i, j, w; cin >> i >> j >> w; tunnel.push_back(Tunnel(i, j, w)); } kruskal(); return 0; }