Advertisement
Guest User

схема

a guest
May 22nd, 2017
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.09 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <cstring>
  6. #include <string>
  7. #include <algorithm>
  8. using namespace std;
  9.  
  10. #define ll long long
  11. #define mp make_pair
  12. const int N = 100;
  13. const int M = 400000;
  14.  
  15. int parent[M];
  16. int set_size[M];
  17. vector<pair<int, pair<int, int>>> edges;
  18. vector<pair<int, int>> ans;
  19. int w = 0, cnt = 0;
  20.  
  21. void make_sets(int v)
  22. {
  23.     parent[v] = v;
  24.     set_size[v] = 1;
  25. }
  26.  
  27. int find_set(int v)
  28. {
  29.     if (parent[v] != v)
  30.         parent[v] = find_set(parent[v]);
  31.     return parent[v];
  32. }
  33.  
  34. void union_sets(int a, int b)
  35. {
  36.     a = find_set(a);
  37.     b = find_set(b);
  38.     if (a != b) {
  39.         if (set_size[b] > set_size[a])
  40.             swap(a, b);
  41.         parent[b] = a;
  42.         set_size[a] += set_size[b];
  43.     }
  44. }
  45.  
  46. int main()
  47. {
  48.     freopen("input.txt", "r", stdin);
  49.     freopen("output.txt", "w", stdout);
  50.  
  51.     int n, m;
  52.     cin >> n >> m;
  53.  
  54.     for (int i = 0; i < n; ++i)
  55.         for (int j = 0; j < m; ++j) {
  56.             int x;
  57.             cin >> x;
  58.             if (x == 1) {
  59.                 edges.push_back(mp(0, mp(i * m + j, i * m + m + j)));
  60.                 edges.push_back(mp(2, mp(i * m + j, i * m + j + 1)));
  61.             }
  62.             else if (x == 2) {
  63.                 edges.push_back(mp(0, mp(i * m + j, i * m + j + 1)));
  64.                 edges.push_back(mp(1, mp(i * m + j, i * m + m + j)));
  65.             }
  66.             else if (x == 3) {
  67.                 edges.push_back(mp(0, mp(i * m + j, i * m + m + j)));
  68.                 edges.push_back(mp(0, mp(i * m + j, i * m + j + 1)));
  69.             }
  70.             else {
  71.                 edges.push_back(mp(1, mp(i * m + j, i * m + m + j)));
  72.                 edges.push_back(mp(2, mp(i * m + j, i * m + j + 1)));
  73.             }
  74.         }
  75.  
  76.     for (int i = 0; i < n * m; ++i)
  77.         make_sets(i);
  78.  
  79.     sort(edges.begin(), edges.end());
  80.  
  81.     for (size_t i = 0; i < edges.size(); ++i) {
  82.         int a = edges[i].second.first;
  83.         int b = edges[i].second.second;
  84.         int x = edges[i].first;
  85.         if (find_set(a) != find_set(b)) {
  86.             union_sets(a, b);
  87.             if (x != 0) {
  88.                 cnt++;
  89.                 w += x;
  90.                 ans.push_back(mp(a, x));
  91.             }
  92.         }
  93.     }
  94.  
  95.     cout << cnt << ' ' << w << endl;
  96.  
  97.     for (size_t i = 0; i < ans.size(); ++i)
  98.         cout << ans[i].first / m + 1 << ' ' << ans[i].first % m + 1 << ' ' << ans[i].second << endl;
  99.  
  100.     fclose(stdin);
  101.     fclose(stdout);
  102.  
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement