수다닷컴

트리의 분할

N개의 정점과 이들 사이에 가중치를 갖는 간선으로 이루어진 트리가 있다. 주어진 자연수 K (K
그림 1
예를 들어 그림 1과 같이 7개의 정점으로 이루어진 트리에서 1번, 2번 정점을 선택하여 그래프를 만들면 그림 2의 (A)와 같이 되고, 나머지 정점들로 그래프를 만들면 그림 2의 (B)와 같이 된다.

그림 2
또한 그림 1의 트리에서 3번, 4번 정점을 선택한 경우 마찬가지로 그림 3의 (A), (B)와 같이 두 그래프가 만들어진다. 그림 3
그림 2의 두 그래프에서 모든 간선의 가중치의 합은 10 + 20 + 10 + 25 = 65가 되고 그림 3의 두 그래프에서 모든 간선의 가중치의 합은 10이 된다.
트리에 대한 정보와 K가 주어질 때, K개의 정점을 선택하여 위와 같은 방법으로 만들어진 두 그래프에 있는 모든 간선의 가중치 합의 최소값을 구하는 프로그램을 작성하시오.
실행 파일의 이름은 TREE.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수가 주어질 수 있다.

입력 형식
입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄에는 N과 K가 빈칸을 사이에 두고 차례로 주어진다. 트리의 정점에는 1번부터 N번까지 번호가 매겨진다. 이어 둘째 줄부터 N-1개의 줄의 각 줄에는 간선 하나의 정보가 주어진다. 간선의 정보는 양 끝 정점 번호와 가중치가 빈 칸을 사이에 두고 차례대로 주어진다. N은 1000이하의 자연수, K는 N보다 작은 자연수이고 간선의 가중치는 1000이하의 자연수이다.

출력 형식
출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에 K개 정점을 선택하여 만들어진 두 개의 그래프에 있는 모든 간선의 가중치 합의 최소값을 출력하고, 둘째 줄에 그 때 선택한 K개 정점들의 번호를 오름차순으로 빈칸을 사이에 두고 한 줄에 출력한다. K개의 정점을 선택하는 방법이 둘 이상인 경우 그 중 한 경우만 출력한다. 입력과 출력의 예
벡터 컨테이너로 인접 리스트 형식으로 나열하고 가중치 내림순으로 정렬한 다음 하나씩 제거해서 작업하면 되는 줄 알았더니 답과 틀리게 나오네요...ㅡㅡ; 매 번 지우면서 정점에 연결된 간선이 얼마나 남아있는지 일일히 확인하는 과정을 넣을까 생각했지만 너무 계산과정이 많아지는 것 같고.......
이 문제를 어떻게 풀어야 될까요?? ..

신청하기