ARCTIC 문제 프림으로 MST 구하면 정답인데 크루스칼로 구현하면 오답입니다.

  • wurikiji
    wurikiji

    해당 문제를 프림 알고리즘으로 MST 를 구하면 정답으로 패스 합니다. 그런데 아래의 코드 처럼 유니온-파인드를 써서 크루스칼알고리즘을 구현했는데, 제가 놓친 부분이 있을까요?

    #include <algorithm>
    #include <iomanip>
    #include <iostream>
    #include <queue>
    #include <vector>
    
    using namespace std;
    
    int c, n;
    vector<int> u(101);
    vector<int> u_size(101, 0);
    
    int find(int idx) {
      if (idx == u[idx]) return idx;
      return u[idx] = find(u[idx]);
    }
    
    int unite(int a, int b) {
      int ua = u[a];
      int ub = u[b];
      u_size[ua] += u_size[ub];
      return u[b] = ua;
    }
    
    bool is_same_union(int a, int b) { return find(a) == find(b); }
    
    int main(void) {
      cin >> c;
      while (c--) {
        cin >> n;
        vector<pair<double, double>> v;
        priority_queue<pair<double, pair<int, int>>> pq;
        for (int i = 0; i < n; ++i) {
          double x, y;
          cin >> x >> y;
          v.push_back({x, y});
          u[i] = i;
          u_size[i] = 1;
          for (int j = 0; j < i; ++j) {
            double xdiff = v[j].first - v[i].first;
            double ydiff = v[j].second - v[i].second;
            double dist = xdiff * xdiff + ydiff * ydiff;
            pq.push({-dist, {i, j}});
          }
        }
    
        double ans = 0;
    
        while (!pq.empty()) {
          double dist = -pq.top().first;
          int a = pq.top().second.first;
          int b = pq.top().second.second;
          pq.pop();
          if (!is_same_union(a, b)) {
            int united = unite(a, b);
            ans = max(ans, dist);
            if (u_size[united] == n) {
              break;
            }
          }
        }
    
        cout << setprecision(2) << fixed << sqrt(ans) << "\n";
      }
      return 0;
    }
    

    4달 전
1개의 댓글이 있습니다.
  • wurikiji
    wurikiji

    자문 자답 입니다. unite 함수에서 find 를 쓰는 걸 깜빡했습니다. 해결!


    4달 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.