🏩题目一描述：

K小姐计划去 n 个城市旅行。这些城市之间有 m 条双向道路相连,每条道路都有一个美景值 w 。

K小姐希望选择一些道路,使得最终所有城市恰好被分成两个连通块。她可以获得所有被选择的道路的美景值之和。

现在K小姐想知道,她能获得的最大的美景值是多少?如果初始时这些城市已经形成了两个或更多的连通块,则输出 − 1 。

输入格式
第一行包含两个正整数 n 和 m ,分别表示城市的数量和道路的数量。

接下来 m 行,每行包含三个正整数 u, v, w,表示城市 u 和城市 v 之间有一条美景值为 w 的道路。

输出格式
输出一个整数,表示K小姐能获得的最大美景值。如果初始时这些城市已经形成了两个或更多的连通块,则输出 − 1。

数据范围

• $2\le n\le 10^5$
• $0\le m\le 10^5$
• $1\le u,v\le n$
• $1\le w\le 10^9$

样例1

输入

3 3
1 2 4
2 3 3
1 3 2

输出

7

说明

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

样例2

输入

4 2
1 2 4
3 4 3

输出

0

说明

初始即为两个连通块，无法删除任何边

OJ链接：
https://codefun2000.com/p/P1818

解题思路一：Kruskal 算法 最小生成树（MST，Minimum Spanning Tree）

n, m = map(int, input().split())
total = 0
roads = []
def find(p, x): # 定义一个查找并查集中元素根节点的函数。它实现了路径压缩，使查询更高效。if p[x] != x:p[x] = find(p, p[x])return p[x]
for _ in range(m):u, v, w = map(int, input().split())total += wroads.append((u, v, w))
roads.sort(key = lambda x: x[2]) # 按边的权重对边进行排序，这是Kruskal算法构建MST的关键步骤。
p = list(range(n+1)) # 并查集 初始化并查集，每个节点的父节点初始化为其自身。
cnt = n
maxv = 0
for u, v, w in roads:u = find(p, u)v = find(p, v)if u != v: # 遍历按权重排序的边，使用并查集判断是否形成环，不形成环则加入MST并更新相关变量。p[u] = v # 加入并查集total -= wcnt -= 1maxv = max(maxv, w)if cnt == 1:print(maxv + total)
elif cnt == 2:print(total)
else:print(-1)

解题思路二：

import sys
input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(10**6)def find(p, x):if p[x] != x:p[x] = find(p, p[x])return p[x]def main():n, m = map(int, input().split())roads = []total = 0for _ in range(m):u, v, w = map(int, input().split())roads.append((u, v, w))total += wroads.sort(key=lambda x: x[2])p = list(range(n + 1))cnt = nmaxv = 0for u, v, w in roads:u = find(p, u)v = find(p, v)if u != v:p[u] = vtotal -= wcnt -= 1maxv = max(maxv, w)if cnt == 1:print(total + maxv)elif cnt == 2:print(total)else:print(-1)if __name__ == "__main__":main()

时间复杂度：O(mlogm)
空间复杂度：O(n)

解题思路三：java, c++

import java.io.*;
import java.util.*;public class Main {static int[] p;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] input = br.readLine().split(" ");int n = Integer.parseInt(input[0]);int m = Integer.parseInt(input[1]);int[][] roads = new int[m][3];long total = 0;for (int i = 0; i < m; i++) {input = br.readLine().split(" ");roads[i][0] = Integer.parseInt(input[0]);roads[i][1] = Integer.parseInt(input[1]);roads[i][2] = Integer.parseInt(input[2]);total += roads[i][2];}Arrays.sort(roads, (a, b) -> a[2] - b[2]);p = new int[n + 1];for (int i = 1; i <= n; i++) {p[i] = i;}int cnt = n;int maxv = 0;for (int[] road : roads) {int u = find(road[0]);int v = find(road[1]);if (u != v) {p[u] = v;total -= road[2];cnt--;maxv = Math.max(maxv, road[2]);}}if (cnt == 1) {System.out.println(total + maxv);} else if (cnt == 2) {System.out.println(total);} else {System.out.println(-1);}}static int find(int x) {if (p[x] != x) {p[x] = find(p[x]);}return p[x];}
}#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<int> p;int find(int x) {if (p[x] != x) {p[x] = find(p[x]);}return p[x];
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<vector<int>> roads(m, vector<int>(3));long long total = 0;for (int i = 0; i < m; i++) {cin >> roads[i][0] >> roads[i][1] >> roads[i][2];total += roads[i][2];}sort(roads.begin(), roads.end(), [](const vector<int>& a, const vector<int>& b) {return a[2] < b[2];});p.resize(n + 1);for (int i = 1; i <= n; i++) {p[i] = i;}int cnt = n;int maxv = 0;for (auto& road : roads) {int u = find(road[0]);int v = find(road[1]);if (u != v) {p[u] = v;total -= road[2];cnt--;maxv = max(maxv, road[2]);}}if (cnt == 1) {cout << total + maxv << '\n';} else if (cnt == 2) {cout << total << '\n';} else {cout << -1 << '\n';}return 0;
}

时间复杂度：O(mlogm)
空间复杂度：O(n)

♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠