题目分析

问题本质

在平面上的 $N$ 个点（城市）中，每个点有人口 $k_i$。需要找到最小的 $D$，使得当只连接距离 $\leq D$ 的边时，至少存在一个连通分量，其中可以选出非空子集，其人口总和模 $K$ 等于 0。

关键观察

图论转化

• 城市作为顶点，距离作为边权
• $D$ 是边权的阈值，控制图的连通性
• 随着 $D$ 增大，连通分量逐渐合并

数论条件

对于连通分量，需要存在非空子集 $S$ 满足：

$$\sum_{i \in S} k_i \equiv 0 \pmod{K}$$

由于 $K \leq 30$，这个条件可以用动态规划高效检查。

算法框架

解法：二分答案 + 并查集 + 模K状态维护

步骤1：二分搜索框架

• 二分搜索 $D$ 的范围 $[0, D_{max}]$
• $D_{max}$ 可取最远两点距离
• 精度要求：输出保留三位小数，需要足够精度

步骤2：检查函数设计 对于给定的 $D$：

1. 构建图：连接所有距离 $\leq D$ 的点对
2. 维护连通分量：使用并查集
3. 维护模K信息：每个连通分量维护居民模K的分布

步骤3：模K状态维护 对于每个连通分量，维护一个大小为 $K$ 的布尔数组 possible[r]，表示是否能得到模 $K$ 余 $r$ 的人口和。

合并两个连通分量 $A$ 和 $B$ 时：

• 新的可能余数 = $\{ (a + b) \bmod K \mid a \in A, b \in B \}$
• 这可以通过卷积计算：$O(K^2)$

步骤4：条件检查 对于每个连通分量，检查 possible[0] 是否为真（注意排除空集情况）。

算法细节

优化建图

直接枚举所有 $O(N^2)$ 边对 $N=5\times 10^4$ 不可行，需要优化：

方法1：网格划分

• 将平面划分为 $D \times D$ 的网格
• 每个点只需与相邻网格中的点连接
• 复杂度：$O(N)$ 期望

方法2：Delaunay三角剖分

• 构建Delaunay三角剖分，只考虑三角剖分中的边
• 任何最小生成树边都在Delaunay图中
• 复杂度：$O(N \log N)$

模K状态的高效维护

由于 $K \leq 30$，可以用位运算优化：

• 用32位整数表示可能余数的集合
• 合并时使用位运算：new_mask = (mask1 << pop2) | (mask2 << pop1) | mask1 | mask2
• 需要循环移位处理模运算

空集处理

题目要求非空子集，因此：

• 初始时每个点的状态：possible[k_i % K] = true
• 合并时不单独考虑空集

复杂度分析

时间复杂度

• 二分搜索：$O(\log(\frac{D_{max}}{\epsilon}))$，其中 $\epsilon$ 是精度
• 每次检查：
  • 建图：$O(N)$ 或 $O(N \log N)$（优化后）
  • 并查集操作：$O(N \alpha(N))$
  • 状态合并：$O(K^2)$ 每次合并
• 总复杂度：$O(\log(\frac{1}{\epsilon}) \cdot (N \log N + N \cdot K^2))$

空间复杂度

• 存储点坐标和人口：$O(N)$
• 并查集和状态数组：$O(N \cdot K)$
• 临时边列表：$O(N)$

特殊情况处理

$K = 1$

任何非空子集都满足条件，答案为0（不建任何路）

单个点满足条件

如果某个城市人口 $k_i \equiv 0 \pmod{K}$，那么 $D = 0$ 就是答案

精度处理

• 距离计算使用double精度
• 二分搜索终止条件：$high - low < 10^{-6}$
• 输出时四舍五入到三位小数

实现策略

分阶段实现

1. 暴力版本：小数据测试，$O(N^2)$ 建图
2. 优化建图：实现网格划分或Delaunay三角剖分
3. 状态压缩：用位运算优化模K状态维护

数据结构选择

• 并查集：路径压缩 + 按秩合并
• 网格索引：unordered_map或vector存储网格单元
• 状态表示：bitset或整数位掩码

算法变体

最小生成树方法

不二分答案，而是按边权从小到大加边：

• 初始每个点独立
• 每次加入最短的未使用边
• 合并连通分量并检查条件
• 第一个满足条件的边权就是答案

优点：避免二分，只需一次计算 缺点：排序边需要 $O(N^2 \log N)$ 或优化

随机化方法

由于 $K$ 很小，可以随机采样子集检查：

• 对于每个连通分量，随机采样多个子集
• 检查是否有子集和模K为0
• 概率分析保证正确性

总结

本题的核心在于将几何图连通性问题与数论子集和问题结合。通过二分答案控制图的连通性，利用并查集维护连通分量，并用动态规划或位运算检查模K条件。关键优化点在于高效建图和快速状态合并。由于 $K$ 很小，状态维护的复杂度是可接受的，使得算法在 $N=5\times 10^4$ 的规模下可行。