1251. 하나로

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)
본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: SW Expert Academy)
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define MAX_VERTICES 1000
#define NO_PARENT 0

using namespace std;

typedef double weight_t;

struct Vertex {
    int x;
    int y;

    int parent;
    int rank;
};

struct Edge {
    weight_t weight;

    // ensure u < v
    int u;
    int v;

    bool operator < (const Edge& edge) const {
        return weight < edge.weight;
    }
};

vector<Vertex> vertices(MAX_VERTICES + 1);
int nVertices;

vector<Edge> edges(MAX_VERTICES * MAX_VERTICES + 1);
int nEdges;

double taxRate;

int find(int x) {
    if (vertices[x].parent == NO_PARENT) {
        return x;
    }
    return vertices[x].parent = find(vertices[x].parent);
}

void unite(int u, int v) {
    int pu = find(u);
    int pv = find(v);
    if (pu == pv) {
        return;
    }
    if (vertices[pu].rank < vertices[pv].rank) {
        vertices[pu].parent = pv;
    } else if (vertices[pu].rank > vertices[pv].rank) {
        vertices[pv].parent = pu;
    } else {
        vertices[pv].parent = pu;
        vertices[pu].rank += 1;
    }
}

weight_t minimumSpanningTree() {
    for (int i = 1; i <= nVertices; i++) {
        vertices[i].parent = NO_PARENT;
        vertices[i].rank = 1;
    }
    nEdges = 0;
    for (int i = 1; i <= nVertices; i++) {
        for (int j = 1; j < i; j++) {
            weight_t dx = vertices[i].x - vertices[j].x;
            weight_t dy = vertices[i].y - vertices[j].y;
            edges[nEdges].weight = taxRate * ((dx * dx) + (dy * dy));
            edges[nEdges].u = j;
            edges[nEdges].v = i;
            nEdges++;
        }
    }
    sort(edges.begin(), edges.begin()+nEdges);
    weight_t answer = 0;
    for (int i = 0; i < nEdges; i++) {
        if (find(edges[i].u) != find(edges[i].v)) {
            unite(edges[i].u, edges[i].v);
            answer += edges[i].weight;
        }
    }
    return answer;
}

void init() {
    cin >> nVertices;
    for (int i = 1; i <= nVertices; i++) {
        cin >> vertices[i].x;
    }
    for (int i = 1; i <= nVertices; i++) {
        cin >> vertices[i].y;
    }
    cin >> taxRate;
}

long long testcase() {
    init();
    return llround(minimumSpanningTree());
}

int main()
{
    int T;
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    setbuf(stdout, NULL);
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cout << '#' << tc << ' ' << testcase() << '\n';
    }
    return 0;
}