题解 P5687 【网格图【暂无数据】】

周子衡 · 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))。