문제) 백준 - 최소 스패닝 트리 - 도시 건설
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
전형적인 최소 스패닝 트리 문제입니다. rank를 이용한 Disjointset과 kruskal 알고리즘을 이용하여 최소 비용을 구합니다. 비용의 개수로 모든 도시 연결 여부를 판단하여 -1 또는 절약 예산을 구합니다.
C++ 소스 코드)
Full Code)
GitHub - Chocochip101/BOJ_Solution: BOJ Solutions
BOJ Solutions. Contribute to Chocochip101/BOJ_Solution development by creating an account on GitHub.
github.com
PS) OverFlow를 조심합시다...
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
| [백준] 18427번 - 함께 블록 쌓기 (C++) 문제 및 풀이 (0) | 2022.01.19 |
|---|---|
| [백준] 11562번 - 백양로 브레이크 (C++) 문제 및 풀이 (0) | 2022.01.19 |
| [백준] 2745번 - 진법 변환 (C++) 문제 및 풀이 (0) | 2022.01.18 |
| [백준] 18312 - 시간 (C++) 문제 및 풀이 (0) | 2022.01.17 |
| [백준] 10653번 - 마라톤 2 (C++) 문제 및 풀이 (0) | 2022.01.17 |
댓글