Art_Uspen

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