정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 www.acmicpc.net 1. 풀이 1. 모든 행성 연결, 2. 최소 비용 -> MST이다. 여기서 N이 10만이므로, 모든 간선을 다 고려한다..

0. 문제 주소 https://www.acmicpc.net/problem/1626 1626번: 두 번째로 작은 스패닝 트리 첫째 줄에 그래프의 정점 수 V(1 ≤ V ≤ 50,000)와 에지 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 에지로 연결된 두 정점과 그 에지의 가중치가 주어진다. 음수 가중치는 없으며, 답은 int 범위를 넘지 않는다. 정점 번호는 1보다 크거나 같고, V보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 *** 첫 다이아 문제 *** 기본 아이디어는 다음과 같다. 0. 크루스칼 알고리즘을 이용해 MST를 만든다. 기존 그래프와 별도로 만들어줄 것이고, 사용하지 않은 간선들은 notused_PQ(min heap)에 따로 ..