(4386) 별자리 만들기

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

단계별로 풀어보기

35단계(최소 신장 트리) 3번째

 

 

 

n개 정점에 대해 n(n-1)/2개의 간선이 전부 존재하는 완전 그래프라고 볼 수 있고, 간선의 가중치가 따로 주어지지 않고 양 정점의 값에 따라 정해지기 때문에 간선 정보를 일괄적으로 계산하는 크루스칼 알고리즘을 사용하였다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef pair<double, pair<int, int>> edge;

inline double getdist(pair<double,double> p1, pair<double,double> p2){
  double dx= p1.first-p2.first;
  double dy= p1.second-p2.second;
  
  return sqrt(dx*dx+dy*dy);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> uf(n);
  vector<pair<double,double>> cord(n);
  vector<edge> v;
  
  for(int i=0;i<n;i++)  cin >> cord[i].first >> cord[i].second;
  
  for(int i=1;i<n;i++)  uf[i]= i;
  
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      double dist= getdist(cord[i], cord[j]);
      
      v.push_back({dist,{i,j}});
    }
  }
  
  sort(v.begin(), v.end());
  
  auto find= [&](auto self, int x) -> int {
    if(uf[x]==x)  return x;
    else  return uf[x]= self(self, uf[x]);
  };
  
  auto merge= [&](int x, int y){
    x= find(find, x);
    y= find(find, y);
    
    if(x==y)  return false;
    
    uf[y]= x;
    
    return true;
  };
  
  int cnt= 1;
  double ans= 0;
  
  for(edge elem:v){
    if(merge(elem.second.first, elem.second.second)){
      cnt++;
      ans+= elem.first;
      
      if(cnt==n)  break;
    }
  }
  
  cout << ans;
  
  return 0;
}