최대신장트리 > 문제은행

본문 바로가기


실전대비 Level4

1350 : 최대신장트리

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 192 회    시도횟수: 455 회   



N개의 정점으로 이뤄진 그래프를 입력받은 다음, 해당 그래프의 최대 신장트리를 구하는 프로그램을 작성하라.

 

여기서 신장트리란, 그래프에서 존재하는 임의의 N-1개 간선들을 선택하여 만들어진 트리를 말하며, 최대 신장트리란, 간선들의 가중치의 합이 최대가 되는 경우를 말한다.


입력의 첫 번째 줄에는 그래프의 정점의 개수 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이하의 숫자이다.



입력에 대해 가능한 신장 트리 중 가중치의 합이 최대가 될 때, 해당 합을 출력한다.


[Copy]
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
[Copy]
42




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.