fork download
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5. using namespace std;
  6.  
  7. int get(const int &n, int *&subtree) {
  8. if (subtree[n] == n) return n;
  9. return subtree[n] = get(subtree[n], subtree);
  10. }
  11.  
  12. void merge(const int &a, const int &b, int *&subtree, int *&vertex_rank) {
  13. int ra = get(a, subtree), rb = get(b, subtree);
  14. if (vertex_rank[ra] < vertex_rank[rb]) subtree[ra] = rb;
  15. else if (vertex_rank[rb] < vertex_rank[ra]) subtree[rb] = ra;
  16. else {
  17. subtree[ra] = rb;
  18. vertex_rank[rb]++;
  19. }
  20. }
  21.  
  22. int main()
  23. {
  24. int vertices, edges; // vertices <= edges : Граф является связным.
  25. scanf("%i%i", &vertices, &edges);
  26. vector <pair<int, pair<int, int>>> v(edges);
  27. for (int i = 0; i < edges; ++i) {
  28. scanf("%i", &v[i].second.first); // vertex out
  29. scanf("%i", &v[i].second.second); // vertex in
  30. scanf("%i", &v[i].first); // weight
  31. }
  32. sort(v.begin(), v.end());
  33. int *subtree = new int[vertices];
  34. int *vertex_rank = new int[vertices];
  35. for (int i = 0; i < vertices; i++) {
  36. subtree[i] = i;
  37. vertex_rank[i] = 1;
  38. }
  39. int spanning_tree_weight = 0;
  40. for (int i = 0; i < edges; ++i) {
  41. if (get(v[i].second.first - 1, subtree) != get(v[i].second.second - 1, subtree)) {
  42. spanning_tree_weight += v[i].first;
  43. merge(v[i].second.first - 1, v[i].second.second - 1, subtree, vertex_rank);
  44. }
  45. }
  46. printf("%i", spanning_tree_weight);
  47. delete[] subtree;
  48. delete[] vertex_rank;
  49. return 0;
  50. }
Success #stdin #stdout 0s 5468KB
stdin
7 12
1 2 20
1 7 1
1 6 23
6 7 36
2 7 4
2 3 15
7 3 9
6 5 28
7 5 25
3 4 3
4 5 17
4 7 16
stdout
57