문제 링크
- http://icpc.me/5257
문제 출처
- 2011 BalkanOI Day2 2번
사용 알고리즘
- MST
- Convex Hull
시간복잡도
- $O(N^{\frac {2}{3}}M log M)$
풀이
$\sum_{edge ∈ ST} {edge_t} \times \sum_{edge ∈ ST} {edge_c}$의 최솟값을 구하는 문제입니다. (ST = Spanning Tree)
모든 스패닝 트리에 대해 점 $(\sum edge_t, \sum edge_c)$를 좌표 평면에 찍어봅시다.
최솟값이 OPT라고 한다면 함수 $xy = OPT$ 그래프의 아래쪽에는 점들이 존재하지 않습니다. 또한 함수 $xy = OPT$ 위의 점 (a, b)의 접선 아래쪽에도 점들이 존재하지 않습니다.
즉, 어떤 점 (a, b)가 답의 후보가 되기 위해서는 함수$xy = ab$에서의 접선의 기울기에 대해 가장 아래쪽에 있어야 합니다.
임의의 기울기 $a/b$가 주어졌을 때 가장 아래쪽에 있는 점을 구하는 것은 $edge_t, edge_c$에 a, b를 곱한 값을 기준으로 정렬해주고 MST를 구하면 됩니다.
$255 \times 255$가지의 기울기를 완전탐색하면 주어진 시간 안에 정답을 구할 수 없습니다.
잘 생각해보면 이러한 후보들은 항상 Convex Hull 위에 있다는 것을 알 수 있습니다.
약간 특이한 방법인데, Convex Hull 위에서 분할 정복을 해줄 수 있습니다.
convex hull의 가장 위에 있는 점은 기울기가 $\infty$일 때 가장 아래에 있는 점이 되고, convex hull의 가장 아래쪽에 있는 점은 기울기가 0일 때 가장 아래에 있는 점이 됩니다.
이렇게 양 끝점을 잡고, 두 점을 잇는 직선의 기울기에 대해 가장 아래에 있는 점을 구하는 방식으로 분할 정복을 해주면 convex hull 위에 있는 점들을 모두 구해줄 수 있습니다.
좌표 범위가 [0, X]일 때 Convex Hull 위에는 최대 $O(X^{\frac {2}{3}})$개의 점만 있을 수 있습니다. 그러므로 $O(N^{\frac {2}{3}} M log M)$에 문제를 풀 수 있습니다.