Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <cstring>
- #include <string>
- #include <algorithm>
- using namespace std;
- #define ll long long
- #define mp make_pair
- const int N = 100;
- const int M = 400000;
- int parent[M];
- int set_size[M];
- vector<pair<int, pair<int, int>>> edges;
- vector<pair<int, int>> ans;
- int w = 0, cnt = 0;
- void make_sets(int v)
- {
- parent[v] = v;
- set_size[v] = 1;
- }
- int find_set(int v)
- {
- if (parent[v] != v)
- parent[v] = find_set(parent[v]);
- return parent[v];
- }
- void union_sets(int a, int b)
- {
- a = find_set(a);
- b = find_set(b);
- if (a != b) {
- if (set_size[b] > set_size[a])
- swap(a, b);
- parent[b] = a;
- set_size[a] += set_size[b];
- }
- }
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n, m;
- cin >> n >> m;
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < m; ++j) {
- int x;
- cin >> x;
- if (x == 1) {
- edges.push_back(mp(0, mp(i * m + j, i * m + m + j)));
- edges.push_back(mp(2, mp(i * m + j, i * m + j + 1)));
- }
- else if (x == 2) {
- edges.push_back(mp(0, mp(i * m + j, i * m + j + 1)));
- edges.push_back(mp(1, mp(i * m + j, i * m + m + j)));
- }
- else if (x == 3) {
- edges.push_back(mp(0, mp(i * m + j, i * m + m + j)));
- edges.push_back(mp(0, mp(i * m + j, i * m + j + 1)));
- }
- else {
- edges.push_back(mp(1, mp(i * m + j, i * m + m + j)));
- edges.push_back(mp(2, mp(i * m + j, i * m + j + 1)));
- }
- }
- for (int i = 0; i < n * m; ++i)
- make_sets(i);
- sort(edges.begin(), edges.end());
- for (size_t i = 0; i < edges.size(); ++i) {
- int a = edges[i].second.first;
- int b = edges[i].second.second;
- int x = edges[i].first;
- if (find_set(a) != find_set(b)) {
- union_sets(a, b);
- if (x != 0) {
- cnt++;
- w += x;
- ans.push_back(mp(a, x));
- }
- }
- }
- cout << cnt << ' ' << w << endl;
- for (size_t i = 0; i < ans.size(); ++i)
- cout << ans[i].first / m + 1 << ' ' << ans[i].first % m + 1 << ' ' << ans[i].second << endl;
- fclose(stdin);
- fclose(stdout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement