[ Problem Solving :: 백준 ] 1647 / 도시 분할 계획

# Link

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

 

# Code - C++

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>
#include <tuple>
#include <queue>

using namespace std;

#define endl '\n'
#define len(x) (int)(x).length()
#define size(x) (int)(x).size()
#define str(x) to_string(x)
#define error logic_error("line " + str(__LINE__))

// Set up : Definitions
const int MAX = 100'000;
struct Edge { int a, b, c; };

// Set up : Global Variables
int P[MAX+1], R[MAX+1];

// Set up : Functions Declaration
bool operator < (const Edge &u, const Edge &v);
int find(int x);
void merge(int x, int y);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, M;
    cin >> N >> M;
    priority_queue<Edge> pq;
    for (int i=0; i<M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        pq.push({A, B, C});
    }

    // Process
    for (int i=1; i<=N; i++) {
        P[i] = i;
        R[i] = 1;
    }

    int cnt = 0, ans = 0;
    while (cnt < N-2) {
        auto [a, b, c] = pq.top(); pq.pop();

        if (find(a) != find(b)) {
            merge(a, b);
            cnt++, ans += c;
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
bool operator < (const Edge &u, const Edge &v)
{
    return make_tuple(-u.c, u.a, u.b) < make_tuple(-v.c, v.a, v.b);
}

int find(int x)
{
    if (P[x] == x) return x;
    return P[x] = find(P[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);

    if (x == y) return;

    if (R[x] < R[y]) swap(x, y);

    P[y] = x;

    if (R[x] == R[y]) R[x]++;
}

 

 

지적, 조언, 첨언 모두 환영합니다!!!