Advertisement
Josif_tepe

Untitled

Dec 26th, 2022
759
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 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 = 300;
  9. int idx[maxn], sz[maxn];
  10. void init_values() {
  11.     for(int i = 0; i < maxn; i++) {
  12.         idx[i] = i;
  13.         sz[i] = 1;
  14.     }
  15. }
  16. int find_root(int x) {
  17.     while(x != idx[x]) {
  18.         idx[x] = idx[idx[x]];
  19.         x = idx[x];
  20.     }
  21.     return x;
  22. }
  23. bool check(int A, int B) {
  24.     if(find_root(A) == find_root(B)) {
  25.         return true;
  26.     }
  27.     return false;
  28. }
  29. void unite(int A, int B) {
  30.     int root_a = find_root(A);
  31.     int root_b = find_root(B);
  32.     if(root_a != root_b) {
  33.         if(sz[root_a] < sz[root_b]) {
  34.             sz[root_b] += sz[root_a];
  35.             idx[root_a] = idx[root_b];
  36.         }
  37.         else {
  38.             sz[root_a] += sz[root_b];
  39.             idx[root_b] = idx[root_a];
  40.         }
  41.     }
  42. }
  43. int main() {
  44.     init_values();
  45.     int n, m;
  46.     cin >> n >> m;
  47.     vector<pair<int, pair<int, int> > > graph;
  48.     for(int i = 0; i < m; i++) {
  49.         int a, b, c;
  50.         cin >> a >> b >> c;
  51.         graph.push_back(make_pair(c, make_pair(a, b)));
  52.     }
  53.     sort(graph.begin(), graph.end());
  54.     int MST1 = 0;
  55.     vector<pair<int, int> > mst;
  56.     for(int i = 0; i < m; i++) {
  57.         int a = graph[i].second.first;
  58.         int b = graph[i].second.second;
  59.         int c = graph[i].first;
  60.         if(!check(a, b)) {
  61.             unite(a, b);
  62.             MST1 += c;
  63.             mst.push_back(make_pair(a, b));
  64.         }
  65.     }
  66.     int MST2 = 2e9;
  67.     for(int i = 0; i < mst.size(); i++) {
  68.         init_values();
  69.         int cnt = 0;
  70.         int tmp_mst = 0;
  71.         for(int j = 0; j < m; j++) {
  72.             int a = graph[j].second.first;
  73.             int b = graph[j].second.second;
  74.             int c = graph[j].first;
  75.             if(a == mst[i].first and b == mst[i].second) continue;
  76.             if(!check(a, b)) {
  77.                 unite(a, b);
  78.                 tmp_mst += c;
  79.                 cnt++;
  80.             }
  81.         }
  82.         if(cnt == n - 1) {
  83.             MST2 = min(MST2, tmp_mst);
  84.         }
  85.     }
  86.     cout << MST1 << " " << MST2 << endl;
  87.     return 0;
  88. }
  89.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement