반응형
https://www.acmicpc.net/problem/21924
21924번: 도시 건설
첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두
www.acmicpc.net
[ 문제풀이 ]
1. 모든 간선을 입력받고, ans에 더해줍니다.
2. 입력받은 간선을 길이를 기준으로 오름차순으로 정렬합니다.
3. for문으로 모든 간선을 탐색하면서 Union-Find를 활용하여 이어주고, ans에서 간선을 빼줍니다.
4. for문을 통해 2부터 N번 노드까지 탐색하면서 1번 노드와 부모 노드가 다른 노드가 하나라도 있다면 -1을 출력하고, 그렇지 않다면 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 | #include<iostream> #include<algorithm> #define ll long long using namespace std; struct node { int a; int b; ll c; }; bool cmp(node left, node right) { return left.c < right.c; } int N, M; ll ans; int vect[100001]; node arr[500000]; 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() { scanf("%d %d", &N, &M); for (int i = 1; i <= N; i++) { vect[i] = i; } for (int i = 0; i < M; i++) { scanf("%d %d %lld", &arr[i].a, &arr[i].b, &arr[i].c); ans += arr[i].c; } sort(arr, arr + M, cmp); for (int i = 0; i < M; i++) { const int a = arr[i].a; const int b = arr[i].b; const ll c = arr[i].c; if (Find(a) != Find(b)) { Union(a, b); ans -= c; } } for (int i = 2; i <= N; i++) { if (Find(1) != Find(i)) { printf("-1"); return 0; } } printf("%lld", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 27009번 - Out of Hay (C++) (0) | 2023.03.08 |
|---|---|
| [ 백준 ] 16202번 - MST 게임 (C++) (0) | 2023.03.07 |
| [ 백준 ] 13905번 - 세부 (C++) (0) | 2023.03.05 |
| [ 백준 ] 5972번 - 택배 배송 (C++) (0) | 2023.03.04 |
| [ 백준 ] 14284번 - 간선 이어가기 2 (C++) (0) | 2023.03.03 |