1847 : 트리분할
제한시간: 1000 ms
메모리제한: 256 MB
해결횟수: 3 회
시도횟수: 32 회
N개의 정점과 이들 사이에 가중치를 갖는 간선으로 이루어진 트리가 있다. 주어진 자연수 K(K＜N)에 대해, 주어진 트리에서 K개의 정점을 선택하여 그 정점과 이들 사이에 이어진 간선으로 하나의 그래프를 만들고, 나머지 N-K개의 정점과 그들 사이에 이어진 간선으로 또 하나의 그래프를 만들려고 한다.
예를 들어 <그림 1>과 같이 7개의 정점으로 이루어진 트리에서 1번, 2번 정점을 선택하여 그래프를 만들려면 <그림 2>의 (A)와 같이 되고, 나머지 정점들로 그래프를 만들면 <그림 2>의 (B)와 같이 된다.
또한 <그림 1>의 트리에서 3번, 4번 정점을 선택한 경우 마찬가지로 <그림 3>의 (A),(B)와 같이 두 그래프가 만들어진다.
<그림 2>의 두 그래프에서 모든 간선의 가중치의 합은 10+20+10+25=65가 되고<그림 3>의 두 그래프에서 모든 간선의 가충치의 합은 10이된다.
트리에 대한 정보와 K가 주어질 때, K개의 정점을 선택하여 위와 같은 방법으로 만들어진 두 그래프에 있는 모든 간선의 가중치 합의 최소값을 구하는 프로그램을 작성하시오.
첫째 중에는 N과 K가 빈 칸을 사이에 두고 차례로 주어진다. 트리의 정점에는 1번부터 N번까지 번호가 매겨진다. 이어 둘째 줄부터 N-1개의 각 줄에는 간선 하나의 정보가 주어진다. 간선의 정보는 양 끝 정점 번호와 가중치가 빈 칸을 사이에 두고 차례대도 주어진다. N은 1,000 이하의 자연수, K는 N보다 작은 자연수이고 간선의 가중치는 1,000 이하의 자연수 이다.
첫째 줄에 K개 정점을 선택하여 만들어진 두 개의 그래프에 있는 모든 간선의 가중치 합의 최소값을 출력하고, 둘째 줄에 그 때 선택한 K개 정점들의 번호를 오름차순으로 빈 칸을 사이에 두고 한 줄에 출력한다. K개의 정점을 선택하는 방법이 둘 이상인 경우 그 중 한 경우만 출력한다.
7 2 1 2 10 1 3 15 1 4 30 5 3 20 6 3 10 4 7 2 |
10 3 4 |
출처 : KOI 본선 2006 고5