2020/12/29
10806번: 공중도시
첫 줄에는 도시의 개수 N과 다리의 개수 M이 주어진다. 두 값의 범위는 3 ≤ N ≤ 100,000, N-1 ≤ M ≤ 200,000이다. 그 다음 M개의 줄에 걸쳐 각 줄에는 다리로 직접 연결된 두 도시 C1과 C2가 차례대로 주
www.acmicpc.net
간단한 BCC 문제. Edge-disjoint BCC로 주어진 그래프를 쪼갠 후, JOISC Mergers와 같은 트리를 덮기 위한 경로의 최소 갯수는 ceil(리프/2)이고, 오일러 순으로 정렬한 후 첫번째 값과 가운데 값을 하나씩 차례로 연결해 주면 된다. 중복 간선이 있다는 점에서 단절선 처리에 주의하자.
19297번: MST with Metropolis
The first line contains two integers $n$ and $m$: the number of vertices and edge in the graph, respectively ($1 \leq n \leq 10^5$, $n - 1 \leq m \leq 3 \times 10^5$). Each of the following $m$ lines describes a single edge and contains three integers, $x$
www.acmicpc.net
먼저 전체 그래프의 MST를 만들고, 현재 색칠된 정점들에 대해 그 정점들이 모두 각자 다른 서브트리에 속하도록 몇 개의 간선을 골라 제거하는 전략을 생각해보자. 이 때 제거하는 간선들의 가중치는 최대가 되어야 한다. 각 쿼리에 대해, 그 정점과 인접한 정점들로 구성된 부분 트리에 대해 트리압축을 하자. 그 후, 관찰할 수 있는 것은 삭제되는 간선은 트리압축된 트리의 한 간선에서 최대 하나, 즉 트리 압축된 간선에서의 최댓값 간선이다. 이를 이용하여 트리압축을 하고 나면 DP를 통해 각 컴포넌트에 정확히 하나만 색칠되어 있도록 최대한 많이 간선들을 끊어줄 수 있다.