몇 개를 지워야 행복할까
면접 대비시간 제한0.5초메모리 제한512 MB
각 간선이 어떤 최소 신장 트리에 속하도록 만들기 위해 지워야 할 간선 수의 최솟값을 구해 모두 더한다.
문제
가중치가 붙은 연결 단순 무향 그래프 가 있다. 잘 알려진 최소 신장 트리(MST) 문제를 떠올려 보자. 여기서는 각 간선 에 대해, 가 의 MST에 들어가게 하려면 를 얼마나 고쳐야 하는지를 묻는다. 를 포함하는 MST가 에 이미 있다면 는 에서 행복하다고 하고, 으로 정의한다. 를 포함하는 MST가 하나도 없다면 는 에서 불행하다고 한다. 이때 에서 간선을 몇 개 지워 연결 그래프 을 만들고, 그 안에서 가 행복해지게 할 수 있다. 는 이렇게 가 행복해지는 을 얻으려고 에서 지우는 간선의 최소 개수다.
그림 E.1. 정점이 3개인 완전 그래프.
그림 E.1의 그래프는 정점이 3개, 간선이 3개다. 이 그래프의 MST는 가중치가 1과 2인 간선 두 개로 이루어지므로 그 두 간선은 행복하다. 가중치가 3인 간선을 행복하게 만들려면 행복한 두 간선 중 아무거나 하나만 지우면 된다.
연결 단순 무향 그래프 가 주어지면 모든 간선 의 를 구해 그 총합을 출력한다.
입력
첫째 줄에 그래프의 정점 수 과 간선 수 이 양의 정수로 주어진다. 이고 이다. 정점에는 1번부터 번까지 번호가 붙어 있다.
다음 개 줄에는 각각 양의 정수 , , 가 주어지며, 정점 와 정점 를 잇는 가중치 인 간선을 뜻한다. 가중치는 1 이상 500 이하의 정수다.
주어지는 그래프는 연결되어 있고, 자기 자신을 잇는 간선은 없으며, 같은 정점 쌍을 잇는 간선이 둘 이상 있는 경우도 없다.
출력
첫째 줄에 모든 간선 에 대한 의 합 를 출력한다.