T3. 小红的图上割边 (25分) - 饿了么测试岗编程题

题目描述

小红拿到了一个无向图，她准备删除若干条边,使得最终恰好有2个连通块。小红每次删除一条边后可以获得这条边边权的价值。

现在小红想知道自己能获得的最大价值是多少?

输入描述

第一行输入两个整数n, m,代表节点数量和边的数量。

接下来的m行,每行输入三个正整数u,v, w，代表节点u和节点v有一条边权为w的边。

输出描述

如果该无向图初始的连通块的数量不小干3，则输出-1。否则输出—个整数,代表小红能获得的最大价值。

示例1

输入：
3 3
1 2 4
2 3 3
1 3 2

输出：
7

说明：
删除前两条边即可。这样有两个连通块:节点1和节点3的连通块，节点2自己为个连通块。

输出

输入：
4 2
1 2 4
3 4 3

输出：
0

说明：
初始即为两个连通块,且无法删除任何边(如果删除就会变成3个连通块)。

题解

这道题目可以归类为最小生成树（Minimum Spanning Tree，MST）相关的算法题。具体来说，这里使用了Kruskal算法来构建最小生成树，并通过并查集来维护连通性。

 
 - 解题思路：
 
   1. 构建并查集，并将每个节点初始化为独立的连通块。
   2. 将边按照权值从小到大排序。
   3. 遍历排序后的边，如果边的两个节点不在同一个连通块中，则合并这两个连通块；如果在同一个连通块中，则说明这条边可以删除，累加到删除权值中。
   4. 遍历完所有边后，检查当前连通块的数量：
      - 如果连通块数量大于2，则无法满足要求，输出-1；
      - 如果连通块数量为2，则输出删除权值；
      - 如果连通块数量为1，则说明原始图已经是一颗树，此时需要删除最小生成树中的一条边，使得树分成两个连通块，输出删除权值加上最后一条边的权值。
   
 - 代码描述：
 
   - 使用并查集进行连通性维护，包括 `find` 函数和 `merge` 函数。
 - 初始化并查集的根节点。
   - 读入边的信息，存储为 `{w, {u, v}}` 的形式，其中 `w` 是边的权值，`u` 和 `v` 是边连接的两个节点。
   - 对边按照权值进行排序。
   - 遍历边，按照上述思路处理，并计算删除权值和最后一条边的权值。
   - 最后根据连通块的数量输出结果。