백준
[1922번] 네트워크 연결
2744m
2019. 8. 15. 20:30
www.acmicpc.net
Union Find를 이용해 풀 수 있는 쉬운 문제
입력 받은 경로들의 비용을 기준으로 정렬해서 차례대로 Union을 진행한다.
Union할 수 있을 때 비용들을 누적해서 최종적으로 출력하면 된다.
|
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
|
/*1922번 네트워크 */
#include <iostream>
#include <algorithm>
#define SIZE 1001
using namespace std;
struct info {
int s, e, value;
}V[100000];
bool cmp(const info &a, const info &b) {
if (a.value < b.value) return true;
else if (a.value == b.value) return a.s < b.s;
else return false;
}
int parent[SIZE];
int find(int target) {
if (target == parent[target]) return target;
else return parent[target] = find(parent[target]);
}
void Union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) parent[b] = a;
}
int N, M, sum;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) parent[i] = i;
for (int i = 0; i < M; i++) {
cin >> V[i].s >> V[i].e >> V[i].value;
}
sort(V, V + M, cmp);
for (int i = 0; i < M; i++) {
int a = V[i].s, b = V[i].e;
if (find(parent[a]) != find(parent[b])) {
Union(a, b);
sum += V[i].value;
}
}
cout << sum;
return 0;
}
|
cs |