AC. 梦想

frank_c1

[ZJOI 2014] 星系调查

发布于2017年03月01日 | 暂无评论 | 426阅读 | 线性代数

题意简述

给定nm边的简单无向连通图。每个点对应一个二维平面上的坐标。

q个询问,每次给定u,v,求u,v所有简单路径中,路径权值的最小值。

路径权值定义为,在所有直线中,到路径上所有点对应的坐标的欧几里得距离的平方和的最小值。

1 \le n, q \le 10 ^ 5, m \le n,权值\in [0, 97]

算法讨论

考虑n个点(x_i, y_i)对应的最优直线,不妨设为y = kx + b

注意这里不要和y轴距离混淆了,这里要求的是欧氏距离,即

\sum_{i=1} ^ {n} {\frac{(k x_i + b - y_i) ^ 2} {k ^ 2 + 1}}

这种形式很不爽呐,什么都做不了,展开展开展开!

\frac{1} {k ^ 2 + 1} ( k ^ 2 \sum_{i=1} ^ {n} {x_i ^ 2} - 2k \sum_{i=1} ^ {n} {x_i y_i} + 2kb \sum_{i=1} ^ {n} {x_i} + nb ^ 2 - 2b \sum_{i=1} ^ {n} {y_i} + \sum_{i=1} ^ {n} {y_i ^ 2})

好像求和符号有点多,我们来规定一下,记

X = \sum_{i=1} ^ {n} {x_i}, Y = \sum_{i=1} ^ {n} {y_i}, X_2 = \sum_{i=1} ^ {n} {x_i ^ 2}, Y_2 = \sum_{i=1} ^ {n} {y_i ^ 2}, S = \sum_{i=1} ^ {n} {x_i y_i}

这样看着舒服多了

\frac{1} {k ^ 2 + 1} ( k ^ 2 X_2 - 2k S + 2kb X + nb ^ 2 - 2b Y + Y_2)

考虑k为定值,则原式是关于b的二次函数,极值点在

b = \frac{Y - kX} {n}

代入原式,再整理成关于k的函数。这一波不怎么友善,是一个有理函数,形如

\frac{Ak ^ 2 + Bk + C} {k ^ 2 + 1}

设答案为s,则

\begin{aligned} \frac{Ak ^ 2 + Bk + C} {k ^ 2 + 1} &= s \\ (A - s) k ^ 2 + B k + (C - s) &= 0\end{aligned}

考虑判别式

\Delta = B ^ 2 - 4(A - s)(C - s) = -4 s ^ 2 + 4 (A + C) s + B ^ 2 - 4 AC \ge 0

考虑是一个关于s的上凸的二次函数,显然在\Delta = 0s能取到最小值。

于是就做完啦!再来看一下出题人强行添加的基环树,我们可以各种姿势维护一下6个和,询问时快速汇总一下信息即可。

时间复杂度O(n \log n)