fork download
  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <iostream>
  7. #include <fstream>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 123456
  13. #define MAX 1037471823
  14.  
  15. using namespace std;
  16.  
  17. struct node
  18. {
  19. int x, y, z;
  20. bool operator < (const node &k) const { return z < k.z; }
  21. } c[MS];
  22. int n, m, a, h[345];
  23.  
  24. int Head(int x)
  25. {
  26. while (h[h[x]] != h[x]) h[x] = h[h[x]];
  27. return h[x];
  28. }
  29.  
  30. int main()
  31. {
  32. scanf("%d%d", &n, &m); printf("%d ", n-1);
  33. rep(i, 1, m) scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].z);
  34. rep(i, 1, n) h[i] = i; sort(c+1, c+1+m);
  35. rep(i, 1, m)
  36. {
  37. if (Head(c[i].x) != Head(c[i].y)) h[h[c[i].x]] = h[c[i].y], a++;
  38. if (a == n-1) { printf("%d\n", c[i].z); break; }
  39. }
  40. return 0;
  41. }
Success #stdin #stdout 0s 4796KB
stdin
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
stdout
3 6