[MST] BOJ 10423 전기가 부족해

문제 링크 : www.acmicpc.net/problem/10423

10423번: 전기가 부족해

모든 도시에 전기가 공급되어야 하며, 한 도시가 둘 이상의 발전소에서 전기를 공급받지 않아야 한다는 점에서 MST를 구하는 문제로 접근할 수 있다.

둘 이상의 발전소에서 전기를 공급받지 않아야 한다는 것은 곧 사이클 없이 모든 정점을 잇는 것과 같기 때문이다.

단, 일반적인 MST 문제와의 차이는 아래의 예제와 같이 모든 정점이 서로 연결되어 있지는 않다는 점이다.

예제의 정답

 

이는 최초 발전기가 설치된 도시의 개수가 2개 이상이기 때문이다.

즉, 최초 발전기가 설치된 A, B, I 정점이 각각 트리의 root가 된다.

따라서 Prim 알고리즘을 통해, 최초 우선순위 큐에 제시된 발전소들의 간선을 모두 넣은 상태로 MST를 구한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
typedef pair<int, int> p;
 
int n, m, k;
bool gen[1001], visit[1001];
vector<int> gens;
vector<p> adj[1001];
 
int prim() {
    int retval = 0, cnt = k;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pque;
 
    for (int i = 0; i < gens.size(); i++) {
        int num = gens[i];
        for (int j = 0; j < adj[num].size(); j++) {
            pque.push(adj[num][j]);
        }
    }
 
    while (!pque.empty()) {
        p cur = pque.top();
        pque.pop();
 
        int dist = cur.first;
        int node = cur.second;
 
        if (visit[node]) continue;
        visit[node] = true;
        retval += dist;
        cnt++;
        if (cnt == n) break;
 
        for (int i = 0; i < adj[node].size(); i++) {
            int next = adj[node][i].second;
            if (visit[next]) continue;
            pque.push({ adj[node][i].first, next });
        }
 
    }
    return retval;
}
 
void init() {
    int g, f, s, w;
    cin >> n >> m >> k;
 
    for (int i = 0; i < k; i++) {
        cin >> g;
        gen[g] = true; visit[g] = true;
        gens.push_back(g);
    }
 
    for (int i = 0; i < m; i++) {
        cin >> f >> s >> w;
        adj[f].push_back({ w, s });
        adj[s].push_back({ w, f });
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    int answer = prim();
    printf("%d\n", answer);
 
    return 0;
}