Advertisement
Guest User

Untitled

a guest
Mar 29th, 2020
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cmath>
  4. #include <iomanip>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. ifstream fin("spantree.in");
  9. ofstream fout("spantree.out");
  10.  
  11. class vertex {
  12. public:
  13. int x;
  14. int y;
  15. };
  16.  
  17. class Edge {
  18. public:
  19. int initial;
  20. int last;
  21. double weight;
  22. };
  23.  
  24. double calcWeight(vertex initial,vertex last) {
  25. double weight = sqrt(pow((initial.x - last.x),2)+pow((initial.y - last.y),2));
  26. return weight;
  27. }
  28.  
  29. int findSet(int v , int root[]) {
  30. if(root[v] == v)
  31. return v;
  32. return root[v] = findSet(root[v],root);
  33. }
  34.  
  35. bool unite(int u, int v, int rank[],int root[]) {
  36. int rootU = findSet(u, root);
  37. int rootV = findSet(v, root);
  38. if(rootU != rootV) {
  39. if(rank[rootU] < rank[rootV])
  40. swap(rootU,rootV);
  41. root[rootV] = rootU;
  42. if(rank[rootU] == rank[rootV]) {
  43. rank[rootU]++;
  44. }
  45. return true;
  46. }
  47. return false;
  48. }
  49.  
  50. double MSTweight(vertex V[],int vertices, int rank[],int root[]) {
  51. int edges = (vertices - 1)*(vertices)/2;
  52. Edge *E = new Edge[edges];
  53. int k = 0;
  54. for(int i = 0; i < vertices; i++) {
  55. for(int j = i + 1; j < vertices; j++) {
  56. double weight = calcWeight(V[i], V[j]);
  57. Edge e{i,j,weight};
  58. E[k++] = e;
  59. }
  60. }
  61. sort(E,E + edges,[](Edge const &a,Edge const &b)-> bool { return a.weight < b.weight;});
  62. double MSTweight = 0;
  63. for(int i = 0; i < edges; i++) {
  64. if(unite(E[i].initial,E[i].last,rank,root))
  65. MSTweight += E[i].weight;
  66. }
  67. return MSTweight;
  68. }
  69.  
  70. int main() {
  71. int vertices,x,y;
  72. fin >> vertices;
  73. vertex V[vertices];
  74. int rank[vertices];
  75. int root[vertices];
  76. for(int i = 0; i < vertices; i++) {
  77. fin >> x >> y;
  78. vertex v{x,y};
  79. V[i] = v;
  80. rank[i] = 0;
  81. root[i] = i;
  82. }
  83. fout << fixed << setprecision(20) << MSTweight(V,vertices,rank,root);
  84.  
  85. return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement