BOJ)4386 Freckles

문제: icpc.me/4386

N개의 점들이 주어지고 각 점들사이의 가중치는 거리와 비례한다 할 때 MST를 구성하는 문제다.

N이 100밖에 되지 않으니 N^2의 방법으로 간선들을 구해준 후 크루스칼을 돌려주면 된다.

 

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