[백준 16202] MST 게임
문제 16202번: MST 게임 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 풀이 문제 이름에도 나와 있듯 MST(최소 신장 트리)를 사용하는 문제이다. 문제에서 제시한 MST의 조건은, 스패닝 트리를 구성하는 간선의 개수는 N-1개이다. 그래프의 임의의 두 정점을 골랐을 때, 스패닝 트리에 속하는 간선만 이용해서 두 정점을 연결하는 경로를 구성할 수 있어야 한다. 이다. 주어진 그래프에서 MST 값을 구하는 문제인데, 주의할 점은 턴마다 최소..