思路
先把赛时想法搬一部分过来
转化题意, 对于 \(n\) 个带权 \(k\) 的点, 任意两点 \(i, j\) 之间有双向连边, 其边权为 \(w_{i, j} = d_{i, j}\) , 求一最小阈值 \(C\) , 满足对于所有 \(w \leq C\) 的边连接后, 存在一个连通块 \(G\), 使得
\[\sum_{i = 1}^{\lvert G \rvert} (a_i \cdot k_i) \equiv 0 {\pmod K} , a_i \in \{0, 1\} \]容易发现的是, 如果你要选择一些确定的点, 使其在同一连通块下, 那么你是可以求出最小阈值 \(C\) 的, 具体的, 我们可以二分之后 \(\rm{check}\) , 这个是 \(\mathcal{O} (n \log V)\) 的, 其中 \(V\) 是值域, 当然你也可以在确定 \(C\) 的情况下检查是否让老板开心
现在问题转化成了, 如何在一个图的连通块中, 判断是否可能有一些点的点权之和为 \(K\) 的倍数, 这个用可行性 \(\rm{dp}\) 可以解决
所以我们初步可以有一个暴力, 首先实数二分 \(V\) , 在这个基础上你把图的连通块跑出来 \(\mathcal{O} (n)\), 然后对于每个连通块进行可行性 \(\rm{dp}\)
好像还没说可行性 \(\rm{dp}\) 该怎么做
令 \(dp_{i, j}\) 表示考虑到第 \(i\) 个点权, 模 \(K\) 的结果是否能达到 \(j\) , 其中 \(dp_{i, j} \in \{0, 1\}\)
显然有转移
\[\begin{align*} dp_{i, j} \gets dp_{i - 1, j} \\ dp_{i, (j + k_i)} \gets dp_{i - 1, j} \end{align*} \]其中 \(j\) 随时取模, 甚至可以滚掉 \(i\)
总结一下, 首先实数二分当前阈值 \(\mathcal{O} (\log V)\) , 然后跑当前图的情况和可行性 \(\rm{dp}\) \(\mathcal{O} (n\omega)\) , 其中 \(\omega = 30\) , 然后直接判断
总复杂度 \(\mathcal{O} (n \log V)\) , 可以通过本题
写的时候遇到了问题, 不能用 \(\mathcal{O} (n^2)\) 的方式建图, 我们需要在不计算原图的情况下找到连通块, 好像也不影响实现
这个思路看起来复杂度正确, 但是为什么被卡了呢?
分析复杂度, 你发现 \(\rm{bfs}\) 的复杂度就已经趋势了, \(\mathcal{O} (n + n^2)\) 没得跑
考虑怎么优化, 需要一点注意力
你发现根据鸽巢原理, 如果一个连通块的大小 \(\geq k\) , 那么一定可以凑成一个 \(k\) 的倍数
那么我们每次特判一下这个, 发现 \(\rm{bfs}\) 还是很慢, 所以我们要用类似于平面最近点对的方法, 来优化找点
怎么找点优化更大， 这里给出两种方法
确定性算法
同上你知道当一个连通块的大小 \(\geq k\) 时已经有答案了, 所以最大可以有用的连边只有 \(nk\) 级别
考虑用 \(\rm{set}\) 维护 「横坐标和当前点差距不超过 \(C\)」 的点集, 按纵坐标排序
然后对于一个点的连边，找出纵坐标范围在 \([y - C, y + C]\) 之间的所有点，然后依次检验连边
考虑这样做的复杂度
对于一个点, 我们选择的范围 \(\rm{belike}\) :
首先你发现 \(3\) 部分之内的点的个数不超过 \(k\) , \(1, 2\) 两部分各不超过 \(k\)
所以最多是 \(3k\) 个点参与枚举
容易发现时间复杂度是正确的
随机化算法
排序, 旋转, 乱搞, 反正能过
实现
框架
同赛时, 稍微修改一些东西
代码
难点在 \(\rm{set}\) 维护, 也不复杂, 为了大局考虑先不写了
总结
倍数型问题的常见解法
善于通过二分答案来转化成判断类问题
考虑答案的上界常常可以优化问题的复杂度
标签：连边,连通,COCI2015,mathcal,DRZAVA,rm,2016,复杂度,dp From： https://www.cnblogs.com/YzaCsp/p/18639437