fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
57
https://ideone.com/hCBfAo
Минимальный каркас - 3835 eolymp
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!