[1251번] 하나로

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 스패닝 트리

2. union find

최소 스패닝 트리를 형성한다.

아래 알고리즘은 크루스칼 알고리즘을 이용하여 문제를 해결하였다.

소스 코드 : 

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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

#include <iostream> #include <cstdio> #include <algorithm> #include <vector>   using namespace std;   typedef long long ll; typedef pair<ll, ll> pll;   struct info {     int from, to;     ll val; };   vector<int> parent;   ll getDist(pll a, pll b) {     return ((a.first - b.first) * (a.first - b.first)) + ((a.second - b.second) * (a.second - b.second)); }   bool comp(const info &a, const info &b) {     if (a.val == b.val) {         if (a.from == b.from)             return a.to < b.to;         return a.from < b.from;     }     return a.val < b.val; }   int find(int a) {     if (a == parent[a])         return a;       return parent[a] = find(parent[a]); } bool merge(int a, int b) {     a = find(a);     b = find(b);       if (a == b)         return false;       parent[b] = a;     return true; } int main() {     freopen("input.txt", "r", stdin);     int tCase;     scanf("%d", &tCase);     for (int tc = 1; tc <= tCase; tc++) {         int n;         scanf("%d", &n);           vector<pll> pt(n);         vector<info> vc;           parent.clear();         for (int i = 0; i < n; i++)             parent.push_back(i);                  for (int i = 0; i < n; i++)             scanf("%d", &pt[i].first);         for (int i = 0; i < n; i++)             scanf("%d", &pt[i].second);         double tax;         scanf("%lf", &tax);           for (int i = 0; i < n; i++)             for (int j = i + 1; j < n; j++)                 vc.push_back({ i,j,getDist(pt[i], pt[j]) });           sort(vc.begin(), vc.end(), comp);                  ll ans = 0;         for (int i = 0; i < vc.size(); i++) {             int from = vc[i].from;             int to = vc[i].to;             ll val = vc[i].val;             if (merge(from, to))                  ans += val;         }           printf("#%d %lld\n", tc, (ll)(ans * tax + 0.5));     }       return 0; }   Colored by Color Scripter

cs