Art_Uspen

Untitled

May 8th, 2021
501
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)) {
  60.                     uniot_set(reps, ranks, first_v, second_v_vert);
  61.                 }
  62.                 if (find_root(reps, first_v) != find_root(reps, second_v_hor)) {
  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)) {
  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)) {
  71.                     uniot_set(reps, ranks, first_v, second_v_vert);
  72.                 }
  73.             } else if (cell == 0) {
  74.                 graph.emplace_back(1, make_pair(first_v, second_v_vert));
  75.                 graph.emplace_back(2, make_pair(first_v, second_v_hor));
  76.             }
  77.         }
  78.     }
  79.     double cost = 0;
  80.     int count = 0;
  81.     vector<point> points;
  82.     for (size_t i = 0; i < graph.size(); ++i) {
  83.         double weight = graph[i].first;
  84.         int first_v = graph[i].second.first;
  85.         int second_v = graph[i].second.second;
  86.         if (find_root(reps, first_v) != find_root(reps, second_v)) {
  87.             uniot_set(reps, ranks, first_v, second_v);
  88.             cost += weight;
  89.             ++count;
  90.             int str = first_v / M;
  91.             int col = first_v % M;
  92.             points.emplace_back(str, col, weight);
  93.         }
  94.     }
  95.     cout << count << ' ' << cost << '\n';
  96.     for (const auto &point:points) {
  97.         cout << point.str + 1 << " " << point.col + 1 << " " << point.value << "\n";
  98.     }
  99. }
RAW Paste Data