自动搬运

查看原文

来自洛谷，原作者为

	周子衡 Shadow is the light!

搬运于2025-08-24 22:13:25，当前版本为作者最后更新于2019-11-30 23:01:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

求求管理造造数据吧……

仿照$\text{Kruskal}$的思想，先对所有的边权从小到大排序。虽然总边数达到了$O(nm)$的级别，但不同的边权却至多$n+m$个，此步的时间复杂度为$O((n+m)\text{log}(n+m))$。

首先取出最小的边权。不失一般性，下面的讨论基于这个边权出现在行中进行。显然这些边都要连上。

接下来一直向下取，直到取到不是行中的边权为止。此时不可能有环，必须要全取。

对于第一个列中的边权，显然此时也不可能有环，必须要全取。

对于接下来的每一种边权，我们维护两个集合$S_r,S_c$，分别表示已经考虑过的行和列。

对于接下来的每一种行中的边权，可以发现，这一行的$m$个点中，所有出现在$S_c$中的点已和外界联通，而不在$S_c$中的点一定没有连出任何一条边。故行中的边要连的条数为$m-|S_c|$条。

同理，对于每种列中的边权，这种边的条数为$n-|S_r|$条。

可以发现，我们只用到了两个变量$sr=|S_r|,sc=|S_c|$，维护这两个变量即可。

综上，我们的算法是：

• 排序；
• 设最小的边权出自行中，不断分析边权，直到取完了第一个列中的边权；
• 对于之后的边，维护$sr,sc$，对于每个行中的边权$vr$，令$sr=sr+1$，并将$vr\times (m-sc)$累加入答案中；列中边权同理。

总时间复杂度$O((n+m)\text{log}(n+m))$。