库仑力

题意

给定数轴上的 $n$ 个电荷，位置和电量分别为 $x_i$ 和 $q_i$。有两个集合 $A,B$，一些电荷事先已经被分配到 $A,B$ 中的一个。将剩下的电荷中的每一个分配到 $A,B$ 之一，使得 $A,B$ 非空且属于同一集合的两个电荷之间的最小库仑力最大。

解析

这个最小库仑力一定是 $\binom{n}{2}$ 个电荷对中的某一对之间的库仑力。二分答案，将那些因为之间库仑力小于答案而不能分配到同一集合的电荷对连边，然后判断能否黑白染色 (是否是二分图)，即可做到 $O(n^2\log n)$ 的复杂度。进一步地，我们可以按边权 (两点之间边的边权为它们之间的库仑力) 从小到大加边，在加边的过程中判断能否黑白染色，省去二分的过程 (由于排序，复杂度仍为 $O(n^2\log n)$)。

按边权排序，然后加边：这很像 Kruskal 算法的过程。如果我们保留原图的一棵最小生成树，对其黑白染色，是否也能得到最优方案？答案是肯定的。

证明

与原过程不同之处在于，Kruskal 算法不加那些成环的边。

• 若一条边成奇环，则其不论在原过程还是在最小生成树对应的方案中都因连接了同色点会被计入答案。
• 若一条边成偶环，则其不论在原过程还是在最小生成树对应的方案中都因连接了异色点而不会被计入答案。

故忽略这些点，也能得到同样的答案。

当然，这棵最小生成树不能用 Kruskal 来求。考虑使用 Borůvka 算法 求稠密图最小生成树。

每次迭代过程中，我们要对每个连通块求出从另一个连通块连向它的边权最小的边。根据库仑定律，两个电荷之间的库仑力正比于 $\dfrac{q_iq_j}{(x_i-x_j)^2}$，那么对于三个电荷 $a,b,c$ ($x_a<x_b<x_c$)，若 $b$ 与 $c$ 之间的库仑力小于等于 $a$ 与 $c$ 之间的库仑力，即

$$\begin{aligned} \dfrac{q_b}{(x_c-x_b)^2}&\le\dfrac{q_a}{(x_c-x_a)^2}\\ \dfrac{q_b}{q_a}&\le\left(\dfrac{x_c-x_b}{x_c-x_a}\right)^2 \end{aligned}$$

考虑 $f(x_a,x_b,x_c)=\dfrac{x_c-x_b}{x_c-x_a}$ 关于 $x_c$ 的偏导数为 $f_{x_c}^\prime(x_a,x_b,x_c)=\dfrac{x_b-x_a}{(x_c-x_a)^2}$，其值总是大于 $0$。故一旦 $b$ 在 $c$ 处库仑力比 $a$ 的小，在 $c$ 右边的任何位置处都将继续比 $a$ 的库仑力小。这是一个自无关的决策单调性，可以 $O(n\log n)$ 分治求。

然而，若我们对每个连通块都这样求一次，总复杂度可达 $O(n^2\log n)$。只要对连通块二进制分组 (本质上也是一种分治) 就可以做到 $O(n\log^2n)$ 的复杂度。

求出最小生成树后，我们再 $O(n\log n)$ 统计答案。Borůvka 至多进行 $O(\log n)$ 次迭代，因此总复杂度为 $O(n\log^3n)$。

实现

不会写

来源

NOI.AC #2122 库仑力

评论