1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 200010; 4 struct edge { 5 int a, b, w; 6 friend bool operator < (edge e1, edge e2) { 7 return e1.w < e2.w; 8 } 9 } edges[N]; 10 int n, m; 11 int p[N]; //并查集里面的p 12 int find(int x) { 13 if (p[x] != x) { 14 p[x] = find(p[x]); 15 } 16 return p[x]; 17 } 18 int main() { 19 cin >> n >> m; 20 for (int i = 0; i < m; i++) { 21 int a, b, w; 22 cin >> a >> b >> w; 23 edges[i].a = a; 24 edges[i].b = b; 25 edges[i].w = w; 26 } 27 sort(edges, edges + m); //1.将所有边按照权重从小到大排序 28 for (int i = 1; i <= n; i++) { //初始化并查集 29 p[i] = i; 30 } 31 int res = 0, cnt = 0; 32 //权重之和，边的数量 33 for (int i = 0; i < m; i++) { //2.从小到大枚举每条边 34 int a = edges[i].a, b = edges[i].b, w = edges[i].w; 35 a = find(a), b = find(b); 36 if (a != b) { //并查集，如果不连通 37 p[a] = b; //加进来 38 res += w; 39 cnt++; 40 } 41 } 42 if (cnt < n - 1) { //不连通 43 cout << "impossible" << endl; 44 } else { 45 cout << res << endl; 46 } 47 return 0; 48 }