반응형
10423번: 전기가 부족해
첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째
www.acmicpc.net
알고리즘 종류
- MST
사고 과정
- 발전소 노드의 부모를 하나로 통일한다. 통일할 노드는 발전소 노드들 중에 가장 작은 노드이다. 이렇게 해결한 이유는 다음과 같다. 일반적인 Kruskal은 하나의 부모 노드로 통일하기 때문에 그래프가 1개 나온다. 하지만, 여기서는 부분 그래프가 나온다. 그래프가 여러 개 나오기 위해서는 부모가 여러 개면 된다.
구현(C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M, K;
vector<pair<pair<int, int>, int> > edges;
int parents[1001];
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
return a.second < b.second;
}
int getParent(int x){
if(parents[x] == x) return x;
return parents[x] = getParent(parents[x]);
}
void unionParents(int a, int b){
a = getParent(a);
b = getParent(b);
if(a > b) parents[b] = a;
else parents[a] = b;
}
void solution(){
sort(edges.begin(), edges.end(), cmp);
int sum=0;
for(int i=0; i<edges.size(); i++){
if(getParent(edges[i].first.first) != getParent(edges[i].first.second)){
sum += edges[i].second;
unionParents(edges[i].first.first, edges[i].first.second);
}
}
cout << sum;
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> K;
for(int i=1; i<=N; i++) parents[i] = i;
// 발전소 노드의 부모를 모두 1개로
int p;
cin >> p;
parents[p] = p;
for(int i=0; i<K-1; i++){
int ps;
cin >> ps;
parents[ps] = p;
}
int u, v, w;
for(int i=0; i<M; i++){
cin >> u >> v >> w;
edges.push_back({{u, v}, w});
}
solution();
}
|
cs |
시행착오
반응형
'코딩 공부 > 백준' 카테고리의 다른 글
[백준][C++] 13459 구슬 탈출 (0) | 2021.03.01 |
---|---|
[백준][C++] 13418 학교 탐방하기 (0) | 2021.02.28 |
[백준][C++] 2352 반도체 설계 (0) | 2021.02.27 |
[백준][C++] 2467 용액 (0) | 2021.02.27 |
[백준][C++] 14719 빗물 (0) | 2021.02.26 |