문제 링크: 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 문제. 단 문제 조건에 따라 Minimum spanning tree가 아닌 "Maximum" spanning tree를 만들어야 한다.
구현은 내 손에 익은 크루스칼로 했는데, union-find를 오랜만에 써봐서 최적화가 잘 되었는지 모르겠다. 업데이트 해야 할 노드가 적은 쪽이 다른 쪽에 붙도록 구현했는데, 이게 맞나...?
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| 17831번 - 대기업 승범이네(python3) (0) | 2021.05.29 |
|---|---|
| 1135번 - 뉴스 전하기(python3) (0) | 2021.05.29 |
| 2533번 - 사회망 서비스(SNS)(python3) (0) | 2021.05.25 |
| 백준 숨바꼭질 시리즈(1697번, 12581번, 13549번, 13913번)(python3) (0) | 2021.03.14 |
| 7453번 - 합이 0인 네 정수(python3) (0) | 2021.03.04 |