Lucent Blog

우선, N-1개의 간선을 선택했다고 할 때, Ci가 가장 작은 간선의 가중치만 최대한 줄이는게 최대인 것은 자명하다.

이를 바탕으로 간단한 해법을 생각해보면, 모든 간선에 대해 해당 간선을 최소간선(Ci가 최소인 간선 - 즉, 가중치를 줄일 간선)으로 고정하고 최소 스패닝 트리를 만들어서 가중치의 합을 계산하는 방식으로 해결할 수 있다는 생각이 든다. 하지만 이는 O(m^2logm)이란 끔찍한 복잡도를 갖기 때문에 아직 문제를 해결하기엔 개선이 필요하다.

하지만 좀 더 생각해보면, 매번 스패닝 트리를 다시 만들지 않고도 각 간선이 최소간선인 최소 스패닝 트리를 전부 탐색해볼 수 있음을 알 수 있다.

1. Wi만 가지고 최소 스패닝 트리를 만든다.

2. 이 스패닝 트리의 Wi의 합을 T라고 하자. 우선 답을 구한다: (답) = T - S / C, 여기서 C는 스패닝 트리의 간선들의 Ci값중 최솟값이다.

3. 해당 스패닝 트리에서 두 정점을 잇는 경로상에서 가장 큰 Wi값을 갖는 간선을 찾는 쿼리(LCA)를 빠르게 할 수 있도록 전처리를 해 둔다. *[LCA]

4. 처음 스패닝 트리에 들어있지 않은 간선들을 모두 순회하면서, 다음과 같은 계산을 한다.

4a. 이 간선을 추가하면 사이클이 생기게 됨이 자명하기 때문에, 이 간선 대신 지워질 간선을 찾아야 한다.

4b. 이 때, 지워지는 간선은 Ai - Bi 경로 상에 있는 간선 중, Wi가 가장 큰 간선이 되어야 함 또한 자명하다(사이클을 이루고 있으니까 어느 간선을 지우든 상관 없다).

4c. 이를 위해 아까 전처리해둔 LCA 쿼리를 한다(이 간선의 인덱스를 j라 하자).

4d. 이 간선이 최소간선일 경우의 답을 계산한다: T - Wj + Wi - S / Ci.

4e. 이게 지금까지의 최솟값보다 더 작은 답이라면 답을 갱신한다.

트리에 한 개씩 간선을 더 붙여보면서 각 경우의 MST를 중복되는 계산 없이 구해본다는 아이디어가 재미있는 해법이다.