티스토리 뷰

ICPC/2014 대전

G. Road Repair

전명우 2014.11.10 00:20

노드가 $N$개인 트리가 주어진다. 트리의 간선에는 비용과 이익 두 가지 값이 있다. 우리는 임의의 경로를 선택하는데 경로에 있는 간선의 비용 합이 C를 넘지 않으면서 이익 합의 최대값을 구하는 문제다. 트리에서 경로는 연결되어 있으면서 경로를 부분 그래프로 봤을 때 정점의 차수가 3을 넘으면 안된다. 즉, 갈래가 없으면 안된다.


이 문제는 IOI 2011 Race 문제와 굉장히 유사한 면이 있다. 우선 분할 정복으로 접근할 수 있다. 이는 트리에서 아래 조건을 만족하는 정점이 항상 존재하기 때문이다. 관련 증명은 Race 문제의 글을 참고하자.


정점이 $N$개인 트리에서 어떤 점을 지웠을 때, 생기는 여러 개의 서브트리 중 정점의 개수가 가장 많은 서브트리의 정점 개수가 $\frac{N}{2}$ 이하다.


위의 조건을 만족하는 정점들 중 하나를 중심 정점이라 하자. 그 중심 정점을 지워 트리를 분할 하고 분할된 서브트리들에 대해서 재귀적으로 문제를 해결하고, 중심 정점을 지나는 경로를 고려하면 된다.


이제 중심 정점을 지나느 경로에 대해서 고려해주면 되는데 이는 중심 정점에서 임의의 정점으로 가는 경로들 중 두 개를 합해서 구할 수 있다. 주의해야할 점은 합칠 두 경로가 중심 정점에서 같은 자식 정점으로 가면 안된다. 즉, 두 경로가 겹치면 안된다. 이를 고려했을 때, 중심 정점을 포함한 이익의 합이 최대인 경로를 찾는 것은 $O(N \lg N)$ 시간복잡도 안에 해결할 수 있다.


이와 같이 분할정복을 할 경우 총 시간복잡도는 $O(N \lg^2 N)$이 된다.


코드 보기

'ICPC > 2014 대전' 카테고리의 다른 글

I. Three Squares  (0) 2014.11.10
H. String Transformation  (0) 2014.11.10
G. Road Repair  (0) 2014.11.10
F. Permutation Cycles  (0) 2014.11.09
E. Marbles  (0) 2014.11.09
D. Exploration  (2) 2014.11.09
댓글
댓글쓰기 폼