Problemas
N개의 정점으로 이뤄진 그래프를 입력받은 다음, 해당 그래프의 최대 신장트리를 구하는 프로그램을 작성하라.
여기서 신장트리란, 그래프에서 존재하는 임의의 N-1개 간선들을 선택하여 만들어진 트리를 말하며, 최대 신장트리란, 간선들의 가중치의 합이 최대가 되는 경우를 말한다.
Entrada
입력의 첫 번째 줄에는 그래프의 정점의 개수 N과 간선의 개수 M이 입력된다. (1≤N≤1,000, 1≤M≤20,000) 두 번째 줄부터 M개의 줄에는 간선의 정보가 입력된다. 간선의 정보는 3개의 숫자 a, b, c로 이뤄지며 해당 간선은 a번 정점과 b번 정점이 연결하고 있으며, 이 간선의 가중치는 c라는 것을 뜻한다. 간선에 방향성은 존재하지 않으나 임의의 두 정점 사이의 간선은 2개 이상이 있을 수 있다. 각 정점은 1번부터 N까지의 번호가 매겨져 있으며 가중치 c는 1이상 100,000이하의 숫자이다.
Salida
입력에 대해 가능한 신장 트리 중 가중치의 합이 최대가 될 때, 해당 합을 출력한다.
Ejemplo
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17
42
Debes iniciar sesión para escribir código.