백준 4386 : 별자리 만들기

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

MST 문제에 있어 입력정보에 애초에 간선에 대한 정보와 가중치가 주어진다면 쉽지만

꼭 간선에 대한 정보가 주어지지 않을 수도 있다.

노드에 대한 정보가 주어지고 그 정보를 토대로 간선 후보를 추출해야 한다.

이 문제의 경우 간선 후보가 될 수 있는 최대 경우의 수가 100*100으로 최대 10만번 연산밖에 안되기때문에

간선 후보를 모든 행성이 연결된 것으로 할 수 있다.

먼저 별에대한 입력정보를 받고 별을 n^2 연산으로 간선을 만들고 Kruskal 알고리즘 적용한다.

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 <cmath> #include <iomanip> #include <algorithm> using namespace std; int n; class Planet{ public: double x, y; Planet(double x = 0, double y = 0) :x(x), y(y) {} }; class Tunnel{ public: int i; int j; double w; Tunnel(int i = 0, int j = 0, double w = 0) :i(i), j(j), w(w) {} bool operator <(const Tunnel &t) const{ return w < t.w; } }; vector<Tunnel> tunnel; Planet planet[101]; int vRoot[101] = {0, }; double ret = 0; double getDist(Planet p1, Planet p2){ return sqrt(pow(p1.x-p2.x, 2) + pow(p1.y-p2.y, 2)); } int findRoot(int v){ if(vRoot[v] == v) return v; return vRoot[v] = findRoot(vRoot[v]); } void kruskal(){ sort(tunnel.begin(), tunnel.end()); for(Tunnel t : tunnel){ int ri = findRoot(t.i); int rj = findRoot(t.j); if(ri != rj){ // no -cycle merge. vRoot[rj] = ri; ret += t.w; } } cout << setprecision(3) << ret << endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1; i <= n; i++){ int x, y; cin >> planet[i].x >> planet[i].y; vRoot[i] = i; } for(int i = 1; i <= n-1; i++){ for(int j = i+1; j <= n; j++){ //set Tunnels tunnel.push_back(Tunnel(i, j, getDist(planet[i], planet[j]))); } } kruskal(); return 0; }