728x90
문제 링크: https://www.acmicpc.net/problem/7044
7044번: Bad Cowtractors
Bessie has been hired to build a cheap internet network among Farmer John's N (2 <= N <= 1,000) barns that are conveniently numbered 1..N. FJ has already done some surveying, and found M (1 <= M <= 20,000) possible connection routes between pairs of barns.
www.acmicpc.net
문제 풀이
최소 스패닝 트리를 이용하는 문제이지만, 문제를 읽어보면 최소 비용이 아닌 최대 비용으로 해줘야한다.
따라서 비용을 내림차순으로 정렬해주자. 또한 MST를 이용하여 완성이 되었다면 간선이 n-1이어야 하는데 그러지 못하는 경우는 -1을 출력해주면 된다.
코드
728x90
'BOJ' 카테고리의 다른 글
| [BOJ][Python] 백준 23056번 - 참가자 명단 (0) | 2021.09.20 |
|---|---|
| [BOJ][Python] 백준 4358번 - 생태학 (0) | 2021.09.20 |
| [BOJ][Python] 백준 23057번 - 도전 숫자왕 (0) | 2021.09.20 |
| [BOJ][Python] 백준 20365번 - 블로그2 (0) | 2021.09.20 |
| [BOJ][Python] 백준 9517번 - 아이 러브 크로아티아 (0) | 2021.09.20 |