# Untitled

May 7th, 2021
559
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <cmath>
3. #include <queue>
4. #include <tuple>
5. #include <vector>
6.
7. using namespace std;
8.
9. struct point {
10.     int x, y;
11.
12.     point(int x_, int y_) :
13.             x(x_), y(y_) {}
14. };
15.
16. int find_root(vector<int> &reps, int vert) {
17.     vector<int> path;
18.     while (reps[vert] != vert) {
19.         path.push_back(vert);
20.         vert = reps[vert];
21.     }
22.     for (size_t i = 0; i < path.size(); ++i) {
23.         reps[path[i]] = vert;
24.     }
25.     return vert;
26. }
27.
28. void uniot_set(vector<int> &reps, vector<int> &ranks, int first_v, int second_v) {
29.     int first_root = find_root(reps, first_v);
30.     int second_root = find_root(reps, second_v);
31.     if (ranks[first_root] > ranks[second_root]) {
32.         reps[second_root] = first_root;
33.     } else if (ranks[first_root] == ranks[second_root]) {
34.         reps[second_root] = first_root;
35.         ++ranks[first_root];
36.     } else {
37.         reps[first_root] = second_root;
38.     }
39. }
40.
41. int main() {
42.     int N;
43.     cin >> N;
44.     vector<point> points;
45.     points.reserve(N);
46.     for (int i = 0; i < N; ++i) {
47.         int x, y;
48.         cin >> x >> y;
49.         points.emplace_back(x, y);
50.     }
51.
52.     vector<int> reps;
53.     reps.assign(N, 0);
54.     for (int i = 0; i < N; ++i) {
55.         reps[i] = i;
56.     }
57.     vector<int> ranks;
58.     ranks.assign(N, 1);
59.     vector<pair<double, pair<int, int>>> graph;
60.     for (int i = 0; i < N; ++i) {
61.         for (int j = i + 1; j < N; ++j) {
62.             double weight = sqrt(pow(points[i].x - points[j].x, 2) + pow(points[i].y - points[j].y, 2));
63.             graph.emplace_back(weight, make_pair(i, j));
64.         }
65.     }
66.     sort(graph.begin(), graph.end());
67.     int M;
68.     cin >> M;
69.     for (int i = 0; i < M; ++i) {
70.         int first_v, second_v;
71.         cin >> first_v >> second_v;
72.         --first_v, --second_v;
73.         uniot_set(reps, ranks, first_v, second_v);
74.     }
75.     double cost = 0;
76.     for (size_t i = 0; i < graph.size(); ++i) {
77.         double weight = graph[i].first;
78.         int first_v = graph[i].second.first;
79.         int second_v = graph[i].second.second;
80.         if (find_root(reps, first_v) != find_root(reps, second_v)) {
81.             uniot_set(reps, ranks, first_v, second_v);
82.             cost += weight;
83.         }
84.     }
85.     cout << cost;
86. }
87.
RAW Paste Data