ARCTIC 문제 프림으로 MST 구하면 정답인데 크루스칼로 구현하면 오답입니다. 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; } 5달 전
1개의 댓글이 있습니다. wurikiji 자문 자답 입니다. unite 함수에서 find 를 쓰는 걸 깜빡했습니다. 해결! 5달 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
wurikiji
해당 문제를 프림 알고리즘으로 MST 를 구하면 정답으로 패스 합니다. 그런데 아래의 코드 처럼 유니온-파인드를 써서 크루스칼알고리즘을 구현했는데, 제가 놓친 부분이 있을까요?
5달 전