[백준 / BOJ] C++ 4343 Arctic Network

4343번: Arctic Network

 

문제

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

4343번: Arctic Network

 

 

풀이

P개의 정점을 연결해야 하는데 두 정점을 연결하는 데는 두 정점의 거리만큼 힘이 필요하다. 또 S개의 정점에 위성 채널을 설치할 수 있는데 위성 채널에 연결된 정점끼리는 통신이 가능하다. 즉, S개의 정점(S-1개의 간선)은 공짜로 연결할 수 있다. 그러므로 각 정점의 좌표를 입력받고 각 좌표 간 거리를 구해 간선을 만든다. 간선의 가중치(정점 간 거리)를 기준으로 오름차순 정렬하고 크루스칼 알고리즘을 사용해 최소 스패닝 트리를 만든다. 이때 P개의 정점을 잇는데 S개의 정점은 미리 이어져 있다고 가정할 수 있으므로 P-S개의 간선을 이어주면 된다. 그리고 가중치 중 최댓값이 답이 되어야 하므로 마지막에 연결된 간선의 가중치가 정답이 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> p;

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

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y)
    p[y] = x;
  else
    p[x] = y;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int S, P, cnt = 0;
    double ans = 0;
    cin >> S >> P;
    p.resize(P + 1);
    iota(p.begin(), p.end(), 0);
    vector<pair<double, pair<int, int>>> edge;
    vector<pair<int, int>> xy(P + 1);
    for (int i = 1; i <= P; i++)
      cin >> xy[i].first >> xy[i].second;
    for (int i = 1; i < P; i++)
      for (int j = i + 1; j <= P; j++) {
        auto [x1, y1] = xy[i];
        auto [x2, y2] = xy[j];
        double d = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
        edge.push_back({d, {i, j}});
      }
    sort(edge.begin(), edge.end());
    for (auto [weight, path] : edge)
      if (find(path.first) != find(path.second)) {
        ans = weight;
        merge(path.first, path.second);
        if (++cnt == P - S)
          break;
      }
    cout.precision(2);
    cout << fixed << ans << '\n';
  }
  return 0;
}