1251. 하나로

MST를 구하는 문제다.

disjoint-set과 크루스칼 알고리즘을 사용했다.

거리의 제곱*환경부담금 E라고 했으므로 거리에 sqrt 씌울 필요 없이 그냥 저장하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
using namespace std;
 
typedef long long ll;
 
struct po {
    ll x, y;
};
 
ll t, n;
double E;
po a[1001];
int p[1001], siz[1001];
 
int f(int x) {
    return x == p[x] ? x : p[x] = f(p[x]);
}
 
int u(int x, int y) {
    x = f(x);
    y = f(y);
    if (x == y) return 0;
    if (siz[x] < siz[y]) swap(x, y);
    p[y] = x;
    if (siz[x] == siz[y]) siz[x]++;
    return 1;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cout << fixed;
    cout.precision(0);
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            p[i] = i;
            siz[i] = 1;
            cin >> a[i].x;
        }
        for (int i = 1; i <= n; ++i)
            cin >> a[i].y;
        cin >> E;
        vector<pair<ll, pair<int, int>>> edges;
        for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j)
            edges.push_back({ (a[i].x - a[j].x)*(a[i].x - a[j].x) + (a[i].y - a[j].y)*(a[i].y - a[j].y),{i,j} });
        sort(edges.begin(), edges.end());
        ll res = 0;
        for (int i = 0;; ++i) {
            if (u(edges[i].second.first, edges[i].second.second)) {
                res += edges[i].first;
                if (--n == 1) 
                    break;
            }
        }
 
        cout << "#" << tc << " " << (double)res*E << '\n';
    }
    return 0;
}