IOI 2005 Rivers

Problem Link

주어지는 마을의 관계가 트리 구조임을 알 수 있다.

0번 노드가 루트인 트리가 구성되는데, 이 트리에서 0번 노드를 제외하고 추가적으로 K개의 목공소를 지어야한다.

단, 목공소를 적절히 배치하여 통나무를 운반하는 비용의 합을 최소화하여야 한다.

동적계획법으로 접근을 해보자.

부분 문제를 정의하고 그 부분 문제에 영향을 미치는 parameter를 고민해보자.

임의의 노드 X이 루트인 부트리에서 K개의 목공소를 배치하는 걸 생각해 볼 수 있겠다.

그런데 여기서 끝나면, 그 부트리에서 최종적으로 상위 조상 중에 어느 목공소로 운반해야하는지 알 수가 없다.

그래서 다음과 같은 3차원 동적계획법 테이블을 정의할 수 있다.

D(L , X , K) : 루트가 X인 부트리에서 K개의 목공소를 배치할 때, 노드 L에 통나무를 운반할 최소 비용.

노드 L은 0번 노드와 X번 노드를 잇는 경로 사이에 존재하겠다.

노드 X의 자식 노드들을 V_1, V_2, ... , V_d라 하자.

다음과 같은 2가지 경우가 있을 수 있다.

1) X에 목공소를 배치하는 경우

V_i를 참조할 때에 L은 X로 변환하여 부분 문제를 정의할 수 있다.

D(L, X, K) = min( D(X, V_i, k) + D_prv(X, V_j, K - k) )

2) X에 목공소를 배치하지 않는 경우

D(L, X, K) = min( D(L, V_i, k) + D_prv(L, V_j, K - k) + W(X) * dist(L~X) )

V_i를 참조할 때에 X에서 V_i에 이르는 거리를 추가하여 계산할 수 있다.

트리에서의 Knapsack 문제를 풀 때와 유사한 방식으로 계산할 수 있으며 전체적인 시간복잡도는 이 된다.