• API
• FAQ
• Tools
• Archive
SHARE
TWEET

Untitled

a guest Mar 26th, 2020 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top