2020/12/29

www.acmicpc.net/problem/10806

10806번: 공중도시

간단한 BCC 문제. Edge-disjoint BCC로 주어진 그래프를 쪼갠 후, JOISC Mergers와 같은 트리를 덮기 위한 경로의 최소 갯수는 ceil(리프/2)이고, 오일러 순으로 정렬한 후 첫번째 값과 가운데 값을 하나씩 차례로 연결해 주면 된다. 중복 간선이 있다는 점에서 단절선 처리에 주의하자.

 

www.acmicpc.net/problem/19297

19297번: MST with Metropolis

먼저 전체 그래프의 MST를 만들고, 현재 색칠된 정점들에 대해 그 정점들이 모두 각자 다른 서브트리에 속하도록 몇 개의 간선을 골라 제거하는 전략을 생각해보자. 이 때 제거하는 간선들의 가중치는 최대가 되어야 한다. 각 쿼리에 대해, 그 정점과 인접한 정점들로 구성된 부분 트리에 대해 트리압축을 하자. 그 후, 관찰할 수 있는 것은 삭제되는 간선은 트리압축된 트리의 한 간선에서 최대 하나, 즉 트리 압축된 간선에서의 최댓값 간선이다. 이를 이용하여 트리압축을 하고 나면 DP를 통해 각 컴포넌트에 정확히 하나만 색칠되어 있도록 최대한 많이 간선들을 끊어줄 수 있다.