220919 문제 풀이 기록
2022. 9. 19. 23:50
P3 | 5915 - Simplifying the Farm
풀이 시간: 1시간 30분
시도 횟수: 무수히 많음
체감 난이도: P3
풀이 쓸 의향: 中
풀이
더보기
크루스칼 MST로 조지면서 가능한 연결 개수 / 연결한 간선 개수 체크하면서 곱해주기. 어떤 MST 하나를 만들 때 사용되는 간선의 가중치 별 개수는 동일하다는 점을 이용함.
여담: 처음에는 Prim으로 짜려다가 너무 복잡해져서 Kruskal로 틀었는데, long long 안해줘서 여러번 틀리고 disjoint set 이상하게 구현해서 자꾸 틀림...
'PS > 풀이 기록장' 카테고리의 다른 글
| 220922 문제 풀이 기록 (0) | 2022.09.23 |
|---|---|
| 220921 문제 풀이 기록 (0) | 2022.09.21 |
| 220918 문제 풀이 기록 (0) | 2022.09.18 |
| 220917 문제 풀이 기록 (0) | 2022.09.18 |
| 220916 문제 풀이 기록 (0) | 2022.09.17 |