가지치기 > 문제은행

본문 바로가기


알고리즘 자료구조2

1563 : 가지치기

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



간선의 가중치가 음수가 아닌 무방향 트리가 주어진다. 하나의 노드는 루트로 주어지며 나머지 노드는 루트로 가는 경로가 유일하다. 루트가 아니면서 자식이 없는 노드는 잎 노드이다.


루트로부터 연결된 간선들 중 일부를 잘라내어 주어진 트리의 모든 잎 노드를 제거하려고 한다. 이때 잘려지는 간선들의 가중치 합이 최소가 되도록 하고 싶다. 이를 구하는 프로그램을 작성하시오.


입력은 여러 개의 테스트 케이스를 포함한다. 각 테스트 케이스의 첫 행은 노드의 개수 N ( 1≤N≤1000) 과 루트가 되는 노드의 번호 R ( 1≤R≤N ) 이 주어진다. 다음 N-1 개의 행에는 노드간의 연결 정보 Ui, Vi( 1≤Ui, Vi≤N), Wi( 0≤Wi≤1000) 가 공백을 구분하여 주어진다. 중복된 간선 정보는 주어지지 않는다. 입력의 끝은 0 0 이다.



각 테스트 케이스에 대하여 트리의 임의의 잎 노드로부터 루트까지 경로가 없도록 모든 잎 노드들을 제거하는데 드는 최소비용의 합을 행으로 구분하여 출력하시오.


[Copy]
15 15
1 2 1
2 3 2
2 5 3
5 6 7
4 6 5
6 7 4
5 15 6
15 10 11
10 13 5
13 14 4
12 13 3
9 10 8
8 9 2
9 11 3
0 0
[Copy]
16


tree, DP

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.