Codeforces Round #378 Problem F

코딩을 너무 안 하는것 같아서 가끔 Codeforces를 풀고있는데, 오랜만에 좋은 문제를 찾았다.

문제를 설명하면 간단하게 N개의 정점과 M개의 가중치를 갖는 무향 간선으로 이루어진 그래프가 주어졌을 때, 모든 정점이 연결돼있도록 N-1개의 간선만 남기되(즉, 스패닝 트리를 만들면 된다), 간선의 가중치의 합이 최소가 되도록 하는 방법을 출력하는 것이다. 여기서 각 간선에는 Wi라는 가중치와 Ci라는 속성이 있는데, 가중치를 원하는 만큼 줄일 수 있지만(0이나 음수로도 줄일 수 있다), 1씩 줄일 때마다 Ci의 비용이 소요되고, 지불할 수 있는 자금의 한계 S가 주어진다.

Link: http://codeforces.com/contest/733/problem/F

우선, 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를 중복되는 계산 없이 구해본다는 아이디어가 재미있는 해법이다.