Algorithm in A..Z - MST (Prim)

개념

MST란 Minimun Spanning Tree의 약어로 최소 신장트리를 뜻한다.

=> 신장트리 중에서 가중치의 합이 최소인 신장트리를 구하는 것

=> 신장트리 : Cycle이 없는 그래프

 

Prim

Heap을 이용하여 MST를 갱신하며 구하는 알고리즘

---

작동원리

1. 시작노드를 우선순위 큐에 PUSH한다.

2. 우선순위 큐에서 노드를 POP한다.

3. 체크되지 않은 노드라면 WEIGHT 값만 큼 RESULT에 더하고 갈 수 있는 노드중 체크되지 않은 노드를 우선순위 큐에 PUSH한다.

4. 2 ~ 3을 우선순위 큐가 EMPTY일 때까지 반복한다.

---

시간복잡도

O(ElogV)

---

문제

13418 학교 탐방하기

www.acmicpc.net/problem/13418

13418번: 학교 탐방하기

---

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int ENTERANCE = 0;

class Node {
public:
    int vertex, distance;

    Node(int vertex = 0, int distance = 0) : vertex(vertex), distance(distance) {

    }

    bool operator<(const Node &o) const {
        return distance < o.distance;
    }

    bool operator>(const Node &o) const {
        return distance > o.distance;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<Node>> map(n + 1);
    m++;
    while (m--) {
        int source, destination, distance;
        cin >> source >> destination >> distance;

        if (distance == 0) {
            map[source].emplace_back(destination, 1);
            map[destination].emplace_back(source, 1);
        } else {
            map[source].emplace_back(destination, -1);
            map[destination].emplace_back(source, -1);
        }
    }

    vector<bool> isChecked(n + 1, false);
    priority_queue<Node, vector<Node>, greater<>> minQueue;
    priority_queue<Node, vector<Node>, less<>> maxQueue;

    int optimize = 0;
    minQueue.emplace(ENTERANCE, 0);
    while (!minQueue.empty()) {
        auto now = minQueue.top(); minQueue.pop();
        if (!isChecked[now.vertex]) {
            //cout << now.vertex << " " << now.distance << endl;
            isChecked[now.vertex] = true;
            if (now.distance == 1) {
                optimize++;
            }

            for (auto &next : map[now.vertex]) {
                if (!isChecked[next.vertex]) {
                    minQueue.emplace(next);
                }
            }
        }
    }

    fill(isChecked.begin(), isChecked.end(), false);

    int worst = 0;
    maxQueue.emplace(ENTERANCE, 0);
    while (!maxQueue.empty()) {
        auto now = maxQueue.top(); maxQueue.pop();

        if (!isChecked[now.vertex]) {
            //cout << now.vertex << " " << now.distance << endl;
            isChecked[now.vertex] = true;
            if (now.distance == 1) {
                worst++;
            }

            for (auto &next : map[now.vertex]) {
                if (!isChecked[next.vertex]) {
                    maxQueue.emplace(next);
                }
            }
        }
    }

    //cout << worst << " " << optimize << endl;
    cout << worst*worst - optimize*optimize << endl;
}