题意

• 有 \(n\) 个岛屿，可以分别花 \(x_i,y_i(1 \le i \le n)\) 的代价在岛屿 \(i\) 建一个机场和港口，一个花 \(z_i(1 \le i \le m)\) 的代价在 \(a_i,b_i\) 之间建一条双向道路。若 \(x\) 和 \(y\) 都有机场或港口或者有道路相连，那么 \(x\) 和 \(y\) 是联通的，问要花至少多少代价使得 \(n\) 个岛屿连通。

• 数据范围：\(2 \le n \le 2 \times 10^5, 1 \le m \le 2 \times 10^5，1 \le x_i,y_i,z_i \le 10^9\)。

思路

• 若只有双向道路，没有机场和港口，那么就非常简单，求一遍最小生成树即可。但是现在这个题有机场和港口的存在，就没那么简单了，那该怎么办了？

• 其实这个题就是再考建图，我们可以对每个 \(i\) 都与 \(n+1\) 连一条边权为 \(x_i\) 的边，也与 \(n+2\) 连一条边权为 \(y_i\) 的边，那么如果 \(i,j\) 都有机场或港口，那么他们可以通过 \(n+1\) 和 \(n+2\) 连在一起，所以现在就可以做最小生成树了。

• 但是这还没完，因为可能用不到机场和港口，所以直接做在 \(MST\) 是不行的，要讨论点 \(n+1,n+2\) 是否算再里面，所以要做四边 \(MST\)。

• 时间复杂度:\(4\) 遍 \(MST\)：\(O(n \log n + m)\)。