백준 10423 (C++) 전기가 부족해

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

10423번: 전기가 부족해

 

 

 

크루스칼 알고리즘

 

 

문제 조건

도시가 연결되어 있는 단위를 (도시 한 개만 존재하는 단위도 포함) 도시 묶음이라 하자.

이 도시 묶음 하나 당 발전소는 단 한 개가 존재해야 한다.

 

(MST에서) 두 노드가 같은 트리 안에 존재할 수 없다는 건
두 노드의 부모노드가 같다는 뜻이다.

 

따라서 발전소의 부모노드를 통일시킨다 (union한다)

발전소 중 하나의 노드를 부모로 삼아도 되지만, 나는 -1로 초기화했다.

 

 

이후 평범한 크루스칼 알고리즘

(벡터에 들어간 두 노드가 연결되었는지 확인, 합침)

을 진행하면 된다.

 

 

---

SMALL

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const int MAX = 1000;
int Parent[MAX];
int N,M,K;
class Edge {
public:
    int s,e,cost;
    Edge(int a, int b, int c) {
        this->s = a;
        this->e = b;
        this->cost = c;
    }
    bool operator<(const Edge &ed) const {
        return this->cost < ed.cost;
    }
};
vector<Edge> v;
int getParent(int n) {
    if (Parent[n] == n) return n;
    else return Parent[n] = getParent(Parent[n]);
}
void unionParent(int n1, int n2) {
    n1 = getParent(n1);
    n2 = getParent(n2);
    if (n1 != n2) Parent[n2] = n1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    int station;
    for (int i = 1; i <= N; i++) Parent[i] = i;
    for (int i = 1; i <= K; i++) {
        cin >> station;
        Parent[station] = -1;
    }
    for (int i = 1; i <= M; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        v.push_back(Edge(a,b,c));
    }
    sort(v.begin(), v.end());
    int ans = 0;
    for (auto cur : v) {
        if (getParent(cur.s) != getParent(cur.e)) {
            unionParent(cur.s, cur.e);
            ans += cur.cost;
        }
    }
    cout << ans << '\n';
   // for (int i = 1; i <= N; i++) cout << Parent[i] << " ";
    return 0;
}