백준 1774 : 우주신과의 교감

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

기본적인 MST 문제이다.

간선이 주어지지 않고 정점의 x,y좌표가 주어졌는데 정점의 개수가 1000개라

모든 정점을 연결하는 후보 간선을 뚫어도 N^2연산으로 충분히 가능하다.

단 조금의 차이점은 미리 다리를 놓은 것인데, 이 경우 연결된 간선의

UnionFind 에서 merge작업만 수행해주면 된다.

즉 각 노드의 루트노드끼리 병합을 수행해주고 일반적인 Kruskal을 진행하기만

하면 된다.

이후 Kruskal을 진행할때 이미 연결한 간선이 나오더라도 이미 root노드가 병합이 되었으므로

그냥 무시하고 넘어가기 때문이다.

※ 단, 부동소수점에 관하여..

보통 소수점 자리수를 맞출때 setprecision을 사용했다.

그러나 이문제에서 setprecision(3)을 설정했더니 채점결과 fail이 떴다..

부동소수점에서 정확도나 출력을 10^2 이런식으로 줄때가 있는데 

setprecision(3) 만 입력할경우 출력해야할 결과가 만약 10.34면 10.3 까지만 출력한다.

3.45같은경우는 3.45출력한다.

fixed되지 않았기때문이다.

따라서 정확하게 소수자리수를 맞추려면

setprecision(3) (정수부분 + 소수부분까지 합쳐서 3자리만 표현)

대신

cout << fixed << setprecision(2) << result << endl;

로 fixed설정하고 2값을 집어넣어야 정확하게 소수 아래 2자리까지만 표현된다.

이렇게 했더니 제대로 4.00이 출력되었고 채점결과 success 받을 수 있었다.

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

#include <iostream> #include <vector> #include <utility> #include <cmath> #include <algorithm> #include <iomanip> #define MAX 1001 using namespace std; int n, m; double cost = 0; pair<int, int> planet[MAX]; class Tunnel{ public: int i, 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; int vRoot[MAX] = {0, }; double getDist(pair<int, int> pla, pair<int, int> plb){ return sqrt(pow(pla.first-plb.first,2)+pow(pla.second-plb.second,2)); } int findRoot(int v){ if(vRoot[v] == v) return v; return vRoot[v] = findRoot(vRoot[v]); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++){ int x, y; cin >> x >> y; planet[i] = make_pair(x, y); vRoot[i] = i; } for(int i = 1; i <= n-1; i++){ for(int j = i+1; j<= n; j++){ tunnel.push_back(Tunnel(i, j, getDist(planet[i], planet[j]))); } } while(m--){ int pa, pb; cin >> pa >> pb; vRoot[findRoot(pb)] = findRoot(pa); } sort(tunnel.begin(), tunnel.end()); for(Tunnel t : tunnel){ int rootI = findRoot(t.i); int rootJ = findRoot(t.j); if(rootI != rootJ){ cost += t.w; vRoot[rootJ] = rootI; } } cout << fixed << setprecision(2) << 10.34 << endl; return 0; }