本题需要前置知识最小生成树。首先判断连通块数量可以通过并查集的方法。考虑连通块为2和1的情况:
时间复杂度为Kruskal算法的时间复杂度O(mlogm)。
小红拿到了一个无向图,她准备删除若干条边,使得最终怡好有2个连通块。小红每次删除一条边后可以获得这条边边权的价值,现在小红想知道自己能获得的最大价值是多少?
第一行输入两个整数n,m,代表节点数量和边的数量。
接下来的m行,每行输入个正整数山4,如,代表节点业和市点有
一条边权为u的边
2≤n≤105
0≤m≤105
1≤u,v≤n
1≤w≤109
如果该无向图初始的连通块的数量不小于3,则输出-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
说明
初始即为两个连通块,无法删除任何边