Art_Uspen

Untitled

May 8th, 2021
762
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cmath>
  4. #include <queue>
  5. #include <tuple>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. struct point {
  11.     int str, col, value;
  12.  
  13.     point(int s_, int c_, int value_) :
  14.             str(s_), col(c_), value(value_) {}
  15. };
  16.  
  17. int find_root(vector<int> &reps, int vert) {
  18.     vector<int> path;
  19.     while (reps[vert] != vert) {
  20.         path.push_back(vert);
  21.         vert = reps[vert];
  22.     }
  23.     for (size_t i = 0; i < path.size(); ++i) {
  24.         reps[path[i]] = vert;
  25.     }
  26.     return vert;
  27. }
  28.  
  29. void uniot_set(vector<int> &reps, vector<int> &ranks, int first_v, int second_v) {
  30.     int first_root = find_root(reps, first_v);
  31.     int second_root = find_root(reps, second_v);
  32.     if (ranks[first_root] > ranks[second_root]) {
  33.         reps[second_root] = first_root;
  34.     } else if (ranks[first_root] == ranks[second_root]) {
  35.         reps[second_root] = first_root;
  36.         ++ranks[first_root];
  37.     } else {
  38.         reps[first_root] = second_root;
  39.     }
  40. }
  41.  
  42. int main() {
  43.     int N, M;
  44.     cin >> N >> M;
  45.     vector<int> reps(N * M, 0);
  46.     for (int i = 0; i < N * M; ++i) {
  47.         reps[i] = i;
  48.     }
  49.     vector<int> ranks(N * M, 1);
  50.     vector<pair<int, pair<int, int>>> graph;
  51.     for (int i = 0; i < N; ++i) {
  52.         for (int j = 0; j < M; ++j) {
  53.             int cell;
  54.             cin >> cell;
  55.             int first_v = i * M + j;
  56.             int second_v_vert = (i * M + M) + j;
  57.             int second_v_hor = i * M + (j + 1);
  58.             if (cell == 3) {
  59.                 if (find_root(reps, first_v) != find_root(reps, second_v_vert) && i != N - 1) {
  60.                     uniot_set(reps, ranks, first_v, second_v_vert);
  61.                 }
  62.                 if (find_root(reps, first_v) != find_root(reps, second_v_hor) && j != M - 1) {
  63.                     uniot_set(reps, ranks, first_v, second_v_hor);
  64.                 }
  65.             } else if (cell == 2) {
  66.                 if (find_root(reps, first_v) != find_root(reps, second_v_hor) && j != M - 1) {
  67.                     uniot_set(reps, ranks, first_v, second_v_hor);
  68.                 }
  69.             } else if (cell == 1) {
  70.                 if (find_root(reps, first_v) != find_root(reps, second_v_vert) && i != N - 1) {
  71.                     uniot_set(reps, ranks, first_v, second_v_vert);
  72.                 }
  73.             } else if (cell == 0) {
  74.                 if (j != M - 1) {
  75.                     graph.emplace_back(2, make_pair(first_v, second_v_hor));
  76.                 }
  77.                 if (i != N - 1) {
  78.                     graph.emplace_back(1, make_pair(first_v, second_v_vert));
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     sort(graph.begin(), graph.end());
  84.     double cost = 0;
  85.     int count = 0;
  86.     vector<point> points;
  87.     for (size_t i = 0; i < graph.size(); ++i) {
  88.         double weight = graph[i].first;
  89.         int first_v = graph[i].second.first;
  90.         int second_v = graph[i].second.second;
  91.         if (find_root(reps, first_v) != find_root(reps, second_v)) {
  92.             uniot_set(reps, ranks, first_v, second_v);
  93.             cost += weight;
  94.             ++count;
  95.             int str = first_v / M;
  96.             int col = first_v % M;
  97.             points.emplace_back(str, col, weight);
  98.         }
  99.     }
  100.     cout << count << ' ' << cost << '\n';
  101.     for (const auto &point:points) {
  102.         cout << point.str + 1 << " " << point.col + 1 << " " << point.value << "\n";
  103.     }
  104. }
RAW Paste Data