Advertisement
Josif_tepe

Untitled

Dec 25th, 2022
941
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <cstring>
  5. #include <queue>
  6. #include <algorithm>
  7. using namespace std;
  8. const int maxn =305;
  9. int idx[maxn], sz[maxn];
  10. int num_of_union;
  11. void reset_val() {
  12.     for(int i = 0; i < maxn; i++) {
  13.         sz[i] = 1;
  14.         idx[i] = i;
  15.     }
  16.     num_of_union = 0;
  17. }
  18. int find_root(int x) {
  19.     while(idx[x] != x) {
  20.         idx[x] = idx[idx[x]];
  21.         x = idx[x];
  22.     }
  23.     return x;
  24. }
  25. bool is_in_the_same_union(int a, int b) {
  26.     if(find_root(a) == find_root(b)) {
  27.         return true;
  28.     }
  29.     return false;
  30. }
  31. void union_two_elems(int a, int b) {
  32.     int root_a = find_root(a);
  33.     int root_b = find_root(b);
  34.     if(root_a != root_b) {
  35.         num_of_union++;
  36.         if(sz[root_a] < sz[root_b]) {
  37.             sz[root_b] += sz[root_a];
  38.             idx[root_a] = idx[root_b];
  39.         }
  40.         else {
  41.             sz[root_a] += sz[root_b];
  42.             idx[root_b] = idx[root_a];
  43.         }
  44.     }
  45. }
  46. int main() {
  47.    
  48.     int n, m;
  49.     cin >> n >> m;
  50.    
  51.     vector<pair<int, pair<int, int> > > graph;
  52.     for(int i = 0; i < m; i++) {
  53.         int a, b, c;
  54.         cin >> a >> b >> c;
  55.         graph.push_back(make_pair(c, make_pair(a, b)));
  56.     }
  57.     sort(graph.begin(), graph.end());
  58.     int MST = 0;
  59.     reset_val();
  60.  
  61.     vector<pair<int, int> > v;
  62.     for(int i = 0; i < m; i++) {
  63.         int c = graph[i].first;
  64.         int a = graph[i].second.first;
  65.         int b = graph[i].second.second;
  66.        
  67.         if(!is_in_the_same_union(a, b)) {
  68.             union_two_elems(a, b);
  69.             v.push_back(make_pair(a, b));
  70.             MST += c;
  71.         }
  72.     }
  73.     int M2 = 2e9;
  74.     for(int i = 0; i < v.size(); i++) {
  75.         int a1 = v[i].first, b1 = v[i].second;
  76.         int mst2 = 0;
  77.         reset_val();
  78.         for(int j =0 ; j < m; j++) {
  79.             if(graph[j].second.first == a1 and graph[j].second.second == b1) continue;
  80.             int c = graph[j].first;
  81.             int a = graph[j].second.first;
  82.             int b = graph[j].second.second;
  83.             if(!is_in_the_same_union(a, b)) {
  84.                 union_two_elems(a, b);
  85.                 mst2 += c;
  86.             }
  87.         }
  88.         if(num_of_union == n - 1) {
  89.             M2 = min(M2, mst2);
  90.         }
  91.     }
  92.     cout << MST << endl << M2 << endl;
  93.     return 0;
  94. }
  95.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement