백준 13418 : 학교 탐방하기

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

Kruskal 알고리즘을 이용한 풀이

단 최소 스패닝 트리 뿐만 아니라 최대 스패닝트리도 동시에 구현해주어야 한다.

Sort() 를 오름차순과 내림차순 두번 구현하는 것 보다 그냥 오름차순으로 한번 sort해주고

최대 스패닝트리를 구할때 reverse_iterator 를 이용해 Unionfind 하여 시간을 단축시킬 수 있었다.

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 65 66 67 68 69 70 71 72

#include <iostream> #include <vector> #include <algorithm> using namespace std; int n, m; class Edge{ public: int i; int j; int 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> edge; int minCost = 0, maxCost = 0; int vRoot[1001] = {0, }; void resetRoot(){ for(int i = 0; i <= n; i++){ vRoot[i] = i; } } int findRoot(int v){ if(vRoot[v] == v) return v; return vRoot[v] = findRoot(vRoot[v]); } void kruskal(){ sort(edge.begin(), edge.end()); resetRoot(); for(Edge e : edge){ int rootI = findRoot(e.i); int rootJ = findRoot(e.j); if(rootI != rootJ){ //no cycle - merge. vRoot[rootJ] = rootI; minCost += e.w; } } resetRoot(); for(auto rit = edge.rbegin(); rit != edge.rend(); rit++){ int rootI = findRoot(rit->i); int rootJ = findRoot(rit->j); if(rootI != rootJ){ vRoot[rootJ] = rootI; maxCost += rit->w; } } cout << (maxCost * maxCost) - (minCost * minCost) << endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; m++; while(m--){ int a, b, c; cin >> a >> b >> c; if(c == 0) c = 1; else c = 0; edge.push_back(Edge(a, b, c)); } kruskal(); return 0; }