Advertisement
Guest User

Untitled

a guest
May 5th, 2015
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.25 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <algorithm>
  5.  
  6. int n, m;
  7. std::vector<std::vector<int> > list(m);
  8.  
  9. struct compare{
  10. bool operator() (std::vector<int> a, std::vector<int> b) {
  11. return a[0] < b[0];
  12. }
  13. } compare;
  14.  
  15. void constructor() {
  16. std::vector<int> v;
  17. int start, finish, cost;
  18. for (size_t i = 0; i != m; i++) {
  19. std::cin >> start >> finish >> cost;
  20. v.push_back(cost);
  21. v.push_back(start);
  22. v.push_back(finish);
  23. // for (size_t i = 0; i < v.size(); i++) {
  24. // std::cout << v[i] << " ";
  25. // }
  26. list.push_back(v);
  27. v = {};
  28.  
  29. }
  30. }
  31.  
  32. void make_set(std::vector<int> &parent) {
  33. for (size_t i = 0; i != list.size(); i++) {
  34. if (parent[list[i][1]] == 0) {
  35. parent[list[i][1]] = list[i][1];
  36. }
  37. if (parent[list[i][2]] == 0) {
  38. parent[list[i][2]] = list[i][2];
  39. }
  40. }
  41. }
  42.  
  43. int find_set(int verties, std::vector<int> &parent) {
  44. if (verties == parent[verties]) {
  45. return verties;
  46. }
  47. return parent[verties] = find_set(parent[verties], parent);
  48. }
  49.  
  50. void union_sets(int parent_a, int parent_b, std::vector<int> &parent, std::vector<int> &rank) {
  51. if (parent_a != parent_b) {
  52. if (rank[parent_a] < rank[parent_b]) {
  53. std::swap(parent_a, parent_b);
  54. }
  55. parent[parent_b] = parent_a;
  56. if (rank[parent_a] == rank[parent_b]) {
  57. rank[parent_a]++;
  58. }
  59. }
  60. }
  61.  
  62. void Kruskal(std::vector<int> &parent, std::vector<int> &rank) {
  63. int number = 0, price = 0;
  64. for (size_t i = 0; i != list.size(); i++) {
  65. if (find_set(list[i][2], parent) != find_set(list[i][1], parent)) {
  66. union_sets(find_set(list[i][2], parent), find_set(list[i][1], parent), parent, rank);
  67. if (list[i][0] != 0) {
  68. price = price + list[i][0];
  69. number++;
  70. }
  71. }
  72. }
  73. std::cout << "\n" << price << " " << number;
  74. }
  75.  
  76. int main() {
  77. std::cin >> n >> m;
  78. std::vector<int> rank(n + 1);
  79. std::vector<int> parent(n + 1);
  80. constructor();
  81. std::sort(list.begin(), list.end(), compare);
  82. make_set(parent);
  83. Kruskal(parent, rank);
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement