Advertisement
Guest User

Untitled

a guest
Mar 26th, 2020
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cmath>
  4. #include <vector>
  5. #include <string>
  6. #define INF 99999999999999
  7. using namespace std;
  8.  
  9. double min = INF;
  10.  
  11. struct Point
  12. {
  13. int x;
  14. int y;
  15. };
  16.  
  17.  
  18. double GetWeight(Point a, Point b)
  19. {
  20. return sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));
  21. }
  22.  
  23. bool NotColored(vector <int>& Marked, int& Vertex)
  24. {
  25. for (int i = 0; i < Marked.size(); ++i)
  26. {
  27. if (Marked[i] == Vertex)
  28. return false;
  29. else
  30. return true;
  31. }
  32. }
  33.  
  34. void MST(vector<int>& Marked, vector<double>& Distance, vector<vector<double>>& Graph, int& V)
  35. {
  36. int index = 0;
  37. for (int i = 0; i < Marked.size(); ++i)
  38. {
  39. for (int j = 0; j < V; ++j)
  40. {
  41. if (NotColored(Marked, j) && Graph[Marked[i]][j] < min)
  42. {
  43. min = Graph[Marked[i]][j];
  44. index = j;
  45. }
  46. }
  47. }
  48. Distance[index] = min;
  49. Marked.push_back(index);
  50. min = INF;
  51.  
  52. if (Marked.size() == V)
  53. {
  54. int result = 0;
  55. for (int i = 0; i < V; ++i)
  56. {
  57. if (!NotColored(Marked, i))
  58. result += Distance[i];
  59. }
  60. cout.precision(10);
  61. cout << result;
  62. exit(0);
  63. }
  64. MST(Marked, Distance, Graph, V);
  65.  
  66.  
  67. }
  68.  
  69. int main()
  70. {
  71. int V, index = 0;
  72. cin >> V;
  73. vector <Point> Points(V);
  74. vector <int> Marked(1);
  75. vector <double> Distance(V, INF);
  76. for (int i = 0; i < V; ++i)
  77. cin >> Points[i].x >> Points[i].y;
  78. vector<vector<double>> Graph(V, vector <double>(V));
  79.  
  80. for (int i = 0; i < V; ++i)
  81. for (int j = 0; j < V; ++j)
  82. Graph[i][j] = GetWeight(Points[i], Points[j]);
  83.  
  84. Marked[0] = 0;
  85.  
  86. for (int i = 1; i < V; ++i)
  87. {
  88. if (Graph[0][i] < min)
  89. {
  90. min = Graph[0][i];
  91. index = i;
  92. }
  93. }
  94. Marked.push_back(index);
  95. Distance[index] = min;
  96. min = INF;
  97.  
  98. MST(Marked, Distance, Graph, V);
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement