(1774) 우주신과의 교감

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

단계별로 풀어보기

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

 

 

 

이미 연결된 통로는 가중치가 0인 간선으로 이어졌다고 볼 수 있다. 이를 전처리로 추가한 뒤 나머지는 별자리 만들기처럼 풀면 된다.

 

 

 

#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);
  cout.precision(2);
  cout << fixed;
  
  int n, m;
  
  cin >> n >> m;
  
  vector<int> uf(n+1);
  vector<pair<double,double>> cord(n+1);
  vector<edge> v;
  
  for(int i=1;i<=n;i++)  cin >> cord[i].first >> cord[i].second;
  
  for(int i=1;i<=n;i++)  uf[i]= i;
  
  for(int i=1;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;
  
  while(m--){
    int a, b;
    
    cin >> a >> b;
    
    cnt+= merge(a,b);
  }
  
  for(edge elem:v){
    if(merge(elem.second.first, elem.second.second)){
      cnt++;
      ans+= elem.first;
    }
    
    if(cnt==n)  break;
  }
  
  cout << ans;
  
  return 0;
}