[백준 / C++] 1647번: 도시 분할 계획

백준 1647번: 도시 분할 계획
알고리즘 분류: 그래프 이론, 최소 스패닝 트리

백준 문제 바로가기

🤨 Hmm...

최소 스패닝 트리 문제! 프림 알고리즘으로 풀어봤다.

마을을 나누는 거는 일단 무시하고 최소 스패닝 트리를 구한 다음 가장 비용이 높은 간선 하나를 끊으면 문제가 원하는 답이 도출된다.

크루스칼도 해야하는데 분리 집합이 무섭다.

+ 히히 크루스칼도 해봤다.

💻 소스 코드

• PrimMST

#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
#define int long long
#define fastIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

class BJ {
    int N, M;
    vector<pair<int, int>> routes[100001];
    bool visited[100001];
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    int answer = 0;
    int MAX = 0;
public:
    BJ();
    void prim(int start);
};

BJ::BJ() {
    cin >> N >> M;
    int a, b, c;
    while (M--) {
        cin >> a >> b >> c;
        routes[a].emplace_back(c, b);
        routes[b].emplace_back(c, a);
        visited[a] = false;
        visited[b] = false;
    }

    prim(a);
    cout << answer - MAX;
}
void BJ::prim(int start) {
    visited[start] = true;
    for (pair<int, int> p : routes[start]) {
        pq.emplace(p);
    }

    int edge = 0;
    while (!pq.empty()) {
        pair<int, int> top = pq.top();
        pq.pop();

        if (visited[top.second]) continue;
        visited[top.second] = true;
        answer += top.first;
        MAX = max(MAX, top.first);
        if (edge == N-1) break;

        for (pair<int, int> p : routes[top.second]) {
            if (visited[p.second]) continue;
            pq.emplace(p);
        }
    }
}

signed main(){
    fastIO;

    BJ a;
}

• KruskalMST

#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
#define int long long
#define fastIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

class BJ {
    int N, M;
    int parent[100001];
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    int answer = 0;
    int MAX = 0;
public:
    BJ();
    void kruskal();
    int findParent(int x);
    void unionParent(int x, int y);
};

BJ::BJ() {
    cin >> N >> M;
    int a, b, c;
    while (M--) {
        cin >> a >> b >> c;
        pq.emplace(c, a, b);
        parent[a] = a;
        parent[b] = b;
    }

    kruskal();
    cout << answer - MAX;
}
void BJ::kruskal() {
    int a, b, c;
    while (!pq.empty()) {
        tie(c, a, b) = pq.top();
        pq.pop();

        if (findParent(a) == findParent(b)) continue;
        unionParent(a, b);
        answer += c;
        MAX = max(MAX, c);
    }
}
int BJ::findParent(int x) {
    if (parent[x] == x)
        return x;
    return findParent(parent[x]);
}
void BJ::unionParent(int x, int y) {
    int px = findParent(x);
    int py = findParent(y);
    if (px <= py)
        parent[py] = px;
    else
        parent[px] = py;
}

signed main(){
    fastIO;

    BJ a;
}