Processing math: 100%
반응형

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

 

10723번: 판게아 1

첫 줄에는 테스트 케이스의 수 T가 정수로 주어진다. 이어서 매 테스트 케이스의 첫 줄에는 도시의 수 n과 도로가 건설된 횟수 m이 공백으로 구분되어 주어진다. 다음 n−1줄에 태초

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, arr 배열에 저장합니다.

 

2. arr 배열을 오름차순으로 정렬합니다.

 

3. 새로운 간선을 입력받을 때마다 mst를 새로 만들어 줍니다.

 

4. 3의 과정에서 새로운 간선이 이전의 mst의 가장 긴 간선보다 길다면 mst를 다시 만들어 줄 필요가 없으므로 넘어갑니다.

 

5. 만들어지는 모든 mst를 XOR 해 ans에 저장합니다.

 

6. 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
struct node {
    int u, v, c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int vect[100000];
vector<node> arr;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int u, int v)
{
    int pu = Find(u);
    int pv = Find(v);
 
    vect[pv] = pu;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int n, m;
        scanf("%d %d", &n, &m);
 
        arr.clear();
 
        for (int i = 1; i < n; i++) {
            int u, c;
            scanf("%d %d", &u, &c);
            arr.push_back({ i,u,c });
        }
 
        int Max = 987654321;
        ll temp = 0;
        ll ans = 0;
 
        for (int i = 0; i < m; i++) {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
 
            arr.push_back({ u,v,c });
 
            if (Max > c) {
                temp = 0;
                Max = 0;
 
                for (int j = 0; j < n; j++) {
                    vect[j] = j;
                }
 
                sort(arr.begin(), arr.end(), cmp);
 
                for (auto& next : arr) {
                    const int u = next.u;
                    const int v = next.v;
                    const int c = next.c;
 
                    if (Find(u) != Find(v)) {
                        Union(u, v);
                        temp += c;
                        Max = max(Max, c);
                    }
                }
            }
            
            if (i == 0) {
                ans = temp;
            }
            else {
                ans ^= temp;
            }
        }
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17

+ Recent posts

티스토리툴바