题目大意

有 $N$ 个星球，每个星球有 $M$ 个城市，形成一个 $N \times M$ 的网格结构：

航线：每个星球内部有 $P$ 条边，连接该星球上的两个城市，维护费用 $c_i$，共 $N \times P$ 条

港口：每个城市编号位置有 $Q$ 条边，连接不同星球的同一编号城市，维护费用 $z_j$，共 $M \times Q$ 条

目标是删除一些边，使得图仍连通，且节省的费用最大（即删除的边权总和最大）。

算法思路

核心思想

将问题转化为求最小生成树，节省的费用 = 原图总边权 - 最小生成树边权。

关键建模技巧

1. 图模型构建

将 $(N + M)$ 个节点视为：

前 $N$ 个节点代表"星球维度"

后 $M$ 个节点代表"城市维度"

航线边 $(e, a_i, b_i, c_i)$ 转化为连接 $(a_i+N)$ 与 $(b_i+N)$，权值 $c_i$

港口边 $(x_j, y_j, f, z_j)$ 转化为连接 $x_j$ 与 $y_j$，权值 $z_j$

2. 最小生成树性质

在最终的生成树中：

需要 $(N + M - 1)$ 条边保持连通

剩余边都可以删除以节省费用

3. 费用计算优化

初始总费用 = $\sum \text{航线费用} \times N + \sum \text{港口费用} \times M$

使用 Kruskal 算法求最小生成树

在合并过程中动态计算节省的费用

算法流程

输入处理：读入所有边，预处理总费用

边排序：按权值从小到大排序

Kruskal 算法：

维护两个计数器 $c_1, c_2$ 分别表示星球和城市维度的连通分量数

合并时根据边类型更新节省的费用

输出结果：总节省费用

复杂度分析

时间复杂度：$O((P+Q)\log(P+Q))$，主要来自排序

空间复杂度：$O(N + M + P + Q)$

总结

本题的巧妙之处在于维度分离建模：

图论建模：将二维网格结构转化为一维并查集问题

最小生成树：利用 Kruskal 算法求最优解

费用计算：通过维护维度连通分量数来高效计算节省费用

这种"维度分离 + MST"的方法可以推广到其他多维连通性问题，体现了图论建模在解决复杂结构问题中的强大能力。