核心思路

将问题转化为图论模型：

顶点：$N$ 个岛屿

边权：$w(i,j) = \max(S_i, S_j)$

关键结论：在该图上的最小生成树（MST） 权重即为 $ans[0]$。 算法步骤

1. 计算基础答案

对完全图求 MST（使用 Kruskal 算法）： $ans[0]=∑e∈MSTmax⁡(Sue,Sve)ans[0]=∑e∈MST​max(Sue​​,Sve​​)$ 2. 处理新增边

对于 $k \geq 1$，每新增一条边可替换 MST 中一条更大边： $ans[k]=ans[k−1]−profit[k]ans[k]=ans[k−1]−profit[k]$

其中 $profit[k]$ 是第 $k$ 条最优新增边的收益。 3. 收益计算

候选边 $(i,j)$ 的收益： $profit=MST路径(i,j)的最大边权−max⁡(Si,Sj)profit=MST路径(i,j)的最大边权−max(Si​,Sj​)$

将正收益按从大到小排序，前 $k$ 项和即为总收益。 复杂度

MST 构建：$O(M \log M)$

收益计算：$O(N \log N)$

总复杂度：$O(N \log N + Q)$