Gi-Log

문제 링크 : https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 모든 행성 간에 플로우를 설치하고 싶지만, 플로우를 설치할 때 사용되는 군대 주둔 비용이 비싸서, 가장 효율적으로 플로우를 설치해야 하는 문제이다. 개인적으로 이런 그래프에서 효율성이나 일의 순서를 파악하는 문제를 보면, 신장 트리와 위상 정렬을 떠올린다. 효율성과 관련된 것은 최소 신장 트리(MST), 일이나 작업 순서를 파악해야하는 문제는 위상 정렬을 이용하며 현재 문제는 최소 ..