[USACO] 백준 1774 - 우주신과의 교감

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

 

2021-08-17 기준 한글 번역의 질이 좋지 못하다는 코멘트가 있는 상황이다. 영어로 문제를 읽을 것을 추천한다.

 

이 문제는 2차원 평면에서 MST(Minimum Spanning Tree)를 완성해야 하는 문제이다.

 

각 정점이 서로 연결되었을 때의 간선들을 전부 생성해서 적절한 방법으로 MST를 구성하여 얻은 가중치의 합이 정답이 된다.

 

시간 복잡도는 간선을 생성하는 과정이 dominant factor이므로 $O(N^{2})$이다.

구현

다른 MST 문제와는 달리 2차원 평면이라 구현에 막연함이 있을 수 있다.

 

우리는 map을 이용하여 각 좌표의 index를 매기고 이 index를 기반으로 유니온 파인드를 만들면 간단하게 구현할 수 있다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int n, m;
map<pii, int> idx;
pii ar[1000];

struct edge
{
  double val;
  pii a, b;

  edge(int x1, int y1, int x2, int y2)
  {
    a = {x1, y1}, b = {x2, y2};
    val = sqrt(double((ll)(x2 - x1) * (x2 - x1) + (ll)(y2 - y1) * (y2 - y1)));
  }

  bool operator < (edge const &arg) const
  {
    return val < arg.val;
  }
};

struct ufind
{
  vector<int> parent, rank;

  ufind(int n): parent(n), rank(n)
  {
    for (int i = 0; i < n; ++i)
      parent[i] = i;
  }

  int find(int x)
  {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
  }

  void vnion(int a, int b)
  {
    a = find(a), b = find(b);

    if (a == b) return;

    if (rank[a] > rank[b])
      swap(a, b);
    
    parent[a] = b;
    if (rank[a] == rank[b])
      ++rank[b];
  }
};

int main()
{
  cout.precision(2);
  cout << fixed;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  cin >> n >> m;

  for (int i = 0; i < n; ++i)
  {
    int a, b;
    cin >> a >> b;
    ar[i].first = a, ar[i].second = b;
    idx[ar[i]] = i;
  }

  ufind st(n);

  vector<edge> edge_list;

  for (int i = 0; i < n; ++i)
  {
    for (int j = i + 1; j < n; ++j)
    {
      edge_list.push_back(edge(ar[i].first, ar[i].second, ar[j].first, ar[j].second));
    }
  }

  sort(edge_list.begin(), edge_list.end());
  int cnt = m;
  double res = 0;

  for (int i = 0; i < m; ++i)
  {
    int go, to;
    cin >> go >> to;
    st.vnion(go - 1, to - 1);
  }

  for (int i = 0; i < edge_list.size(); ++i)
  {
    if (cnt == n - 1)
      break;
    
    if (st.find(idx[edge_list[i].a]) == st.find(idx[edge_list[i].b]))
      continue;
    
    st.vnion(idx[edge_list[i].a], idx[edge_list[i].b]);
    res += edge_list[i].val;
    ++cnt;
  }

  cout << round(res * 100) / 100 << '\n';
}