반응형

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

 

6497번: 전력난

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력받는 모든 길의 거리를 ans에 더해줍니다.

 

2. Union-Find를 이용하여 노드들을 이어지고, 이어 줄 때마다 ans에서 이어진 길의 거리를 빼줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
69
70
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int x;
    int y;
    int z;
};
 
bool cmp(node left, node right)
{
    return left.z < right.z;
}
 
int m, n;
int vect[200000];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    while (1) {
        scanf("%d %d", &m, &n);
        if (m == 0 && n == 0) break;
 
        int ans = 0;
        vector<node> arr;
 
        for (int i = 0; i < m; i++) {
            vect[i] = i;
        }
 
        for (int i = 0; i < n; i++) {
            int x, y, z;
            scanf("%d %d %d", &x, &y, &z);
            arr.push_back({ x,y,z });
            ans += z;
        }
 
        sort(arr.begin(), arr.end(), cmp);
 
        for (auto& next : arr) {
            const int x = next.x;
            const int y = next.y;
            const int z = next.z;
 
            if (Find(x) != Find(y)) {
                Union(x, y);
                ans -= z;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1613번 - 역사 (C++)  (0) 2023.02.24
[ 백준 ] 1162번 - 도로포장 (C++)  (0) 2023.02.23
[ 백준 ] 18223번 - 민준이와 마산 그리고 건우 (C++)  (0) 2023.02.21
[ 백준 ] 2056번 - 작업 (C++)  (0) 2023.02.20
[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19

+ Recent posts

티스토리툴바