문제
https://www.acmicpc.net/problem/10423
문제해설
그래프가 주어진다.
각 노드는 도시들이고 어떠한 도시에는 발전소가 있다.
간선들은 도시를 잇는 케이블인데 각 도로마다 연결하는 비용이 존재한다.
케이블을 잘 연결해 모든 도시가 전기를 쓸 수 있도록 해야한다.
발전소가 있는 도시와 연결되어 있다면 전기를 쓸 수 있다.
또한 추가 조건이 한 도시에 두 발전소가 연결되어 있으면 안된다.
발전소는 무조한 하나만 연결해야 한다.
문제풀이
처음에는 굉장히 어려운 문제라고 생각했다.
하지만 생각해보니 크루스칼을 이용해
엄청 간단하게 풀리는 문제였다.
그냥 처음 시작할때 발전소들을 전부 유니온해서
묶어놓고 MST를 만들면 되는 문제다.
전체코드
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
67
68
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define INF 1000000000
using namespace std;
int parent[1001];
struct edge {
int st, end, cost;
};
bool operator<(edge x, edge y) {
return x.cost > y.cost;
}
priority_queue<edge, vector<edge>>arr;
int find(int x) {
if (parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
parent[y] = x;
}
bool isUnion(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return true;
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m, k; cin >> n >> m >> k;
vector<int>tmp;
for (int i = 0; i < 1001; i++)
parent[i] = i;
for (int i = 0; i < k; i++) {
int x; cin >> x;
tmp.push_back(x);
}
for (int i = 1; i < k; i++)
merge(tmp[i - 1], tmp[i]);
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
arr.push({ a,b,c });
}
int sum = 0;
while (!arr.empty()) {
if (!isUnion(arr.top().st, arr.top().end)) {
sum += arr.top().cost;
merge(arr.top().st, arr.top().end);
}
arr.pop();
}
cout << sum;
return 0;
}