呵呵的最小生成树
——代码
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 5 #define N 100001 6 7 int n, m, sum; 8 int f[N]; 9 10 struct node 11 { 12 int x, y, z; 13 }e[N]; 14 15 inline int read() 16 { 17 int x = 0, f = 1; 18 char ch = getchar(); 19 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 20 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 21 return x * f; 22 } 23 24 inline bool cmp(node x, node y) 25 { 26 return x.z < y.z; 27 } 28 29 inline int find(int x) 30 { 31 return x == f[x] ? x : f[x] = find(f[x]); 32 } 33 34 int main() 35 { 36 int i, j, x, y; 37 n = sum = read(); 38 m = read(); 39 for(i = 1; i <= n; i++) f[i] = i; 40 for(i = 1; i <= m; i++) 41 { 42 e[i].x = read(); 43 e[i].y = read(); 44 e[i].z = read(); 45 } 46 std::sort(e + 1, e + m + 1, cmp); 47 for(i = 1; i <= m; i++) 48 { 49 x = find(e[i].x); 50 y = find(e[i].y); 51 if(x ^ y) 52 { 53 f[x] = y; 54 sum--; 55 if(sum == 1) 56 { 57 printf("%d ", e[i].z); 58 return 0; 59 } 60 } 61 } 62 puts("-1"); 63 return 0; 64 }