BOJ)4343 Arctic Network

문제: icpc.me/4343

P개의 전초기지가 있을 때 S개의 전초기지는 위성채널과 연결되어 있을 때 전초기지 전체가 위성채널과 연결되게 하는데 필요한 마지막 최소 연결비용을 출력하는것이다. 연결비용은 두 전초기지의 거리와 같다.

우리는 P-S개의 간선을 연결하는 MST를 구현하여 마지막으로 연결되는 간선의 가중치를 출력하면 된다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int t, n, m, x, y, par[501], c;
pair<int, int> p[501];
double r;
double calc(pair<int,int> cx,pair<int,int> cy) {
    return sqrt((cx.first - cy.first)*(cx.first - cy.first) + (cx.second - cy.second)*(cx.second - cy.second));
}
void init() {
    for (int i = 1; i <= n; i++)
        par[i] = i;
}
int find(int x) {
    if (x == par[x])return x;
    return par[x] = find(par[x]);
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    c--;
    par[x] = y;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &m, &n);
        init();
        r = 0.0;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &x, &y);
            p[i] = { x,y };
        }
        c = n - m;
        priority_queue<pair<double, pair<int, int>>> pq;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                pq.push({ -calc(p[i],p[j]),{i,j} });
            }
        }
        while (c) {
            r = -pq.top().first;
            x = pq.top().second.first;
            y = pq.top().second.second;
            pq.pop();
            merge(x, y);
        }
        printf("%.2lf\n", r);
    }
    return 0;
}