Advertisement
Josif_tepe

Untitled

Oct 24th, 2023
994
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5. const int maxn = 105;
  6. int root[maxn], sz[maxn];
  7. void init() {
  8.     for(int i = 0; i < maxn; i++) {
  9.         sz[i] = 1;
  10.         root[i] = i;
  11.     }
  12. }
  13. int find_root(int x) {
  14.     while(x != root[x]) {
  15.         root[x] = root[root[x]];
  16.         x = root[x];
  17.     }
  18.     return x;
  19. }
  20. bool check(int A, int B) {
  21.     return find_root(A) == find_root(B);
  22. }
  23. void unite(int A, int B) {
  24.     int a_root = find_root(A);
  25.     int b_root = find_root(B);
  26.     if(a_root != b_root) {
  27.         if(sz[a_root] > sz[b_root]) {
  28.             sz[a_root] += sz[b_root];
  29.             root[b_root] = root[a_root];
  30.         }
  31.         else {
  32.             sz[b_root] += sz[a_root];
  33.             root[a_root] = root[b_root];
  34.         }
  35.     }
  36. }
  37. int main() {
  38.     int n, m;
  39.     cin >> n >> m;
  40.     vector<pair<int, pair<int, int> > > v;
  41.    
  42.     for(int i = 0; i < m; i++) {
  43.         int a, b, c;
  44.         cin >> a >> b >> c;
  45.         v.push_back(make_pair(c, make_pair(a, b)));
  46.     }
  47.     sort(v.begin(), v.end());
  48.     init();
  49.    
  50.     int MST1 = 0;
  51.     vector<pair<int, int> > mst_edges;
  52.     for(int i = 0; i < m; i++) {
  53.         int a = v[i].second.first;
  54.         int b = v[i].second.second;
  55.         int c = v[i].first;
  56.         if(!check(a, b)) {
  57.             unite(a, b);
  58.             MST1 += c;
  59.             mst_edges.push_back(make_pair(a, b));
  60.         }
  61.     }
  62.     int MST2 = 1e9;
  63.     for(int i = 0; i < (int) mst_edges.size(); i++) {
  64.         init();
  65.         int tmp = 0;
  66.         int cnt = 0;
  67.         for(int j = 0; j < m; j++) {
  68.                 int a = v[j].second.first;
  69.                 int b = v[j].second.second;
  70.                 int c = v[j].first;
  71.             if(a == mst_edges[i].first and b == mst_edges[i].second) continue;
  72.            
  73.                 if(!check(a, b)) {
  74.                     unite(a, b);
  75.                     tmp += c;
  76.                     cnt++;
  77.             }
  78.            
  79.         }
  80.         if(cnt == n - 1) {
  81.             MST2 = min(MST2, tmp);
  82.         }
  83.     }
  84.     cout << MST1 << " " << MST2 << endl;
  85.     return 0;
  86. }
  87.  
  88.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement