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` 是边连接的两个节点。 - 对边按照权值进行排序。 - 遍历边,按照上述思路处理,并计算删除权值和最后一条边的权值。 - 最后根据连通块的数量输出结果。
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
🔥笔试编程真题宝典💯 文章被收录于专栏
📕分享大厂机试真题深度剖析核心考点,助你速通面试。