Saleh127

UVA 10600 / 2nd best MST

Sep 26th, 2021
1,027
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  5.  
  6. vector<ll>parent,rankk;
  7. map<pair<ll,ll>,bool>x;
  8. vector<pair<ll,pair<ll,ll>>>edge;
  9.  
  10. void make_set(ll n)
  11. {
  12.     for(ll i=0; i<n; i++)
  13.     {
  14.         parent[i] = i;
  15.         rankk[i] = 0;
  16.     }
  17. }
  18.  
  19. int find_set(ll v)
  20. {
  21.     if (v == parent[v])
  22.     {
  23.         return v;
  24.     }
  25.     return parent[v] = find_set(parent[v]);
  26. }
  27.  
  28. void union_sets(ll a, ll b)
  29. {
  30.     a = find_set(a);
  31.     b = find_set(b);
  32.  
  33.     if (a != b)
  34.     {
  35.         if(rand()%2)
  36.         {
  37.             swap(a,b);
  38.         }
  39.         parent[b]=a;
  40.  
  41.         /* else use this
  42.         if (rankk[a] < rankk[b]){swap(a, b);} parent[b] = a; if (rankk[a] == rankk[b]){rankk[a]++;}
  43.         */
  44.     }
  45. }
  46.  
  47.  
  48. int main()
  49. {
  50.     ios_base::sync_with_stdio(0);
  51.     cin.tie(0);
  52.     cout.tie(0);
  53.  
  54.     test
  55.     {
  56.         ll n,m,i,j,k,l=1,c,d,e;
  57.  
  58.         cin>>n>>m;
  59.  
  60.         edge.clear();
  61.         x.clear();
  62.         parent.resize(n+2);
  63.         rankk.resize(n+2);
  64.         make_set(n+2);
  65.  
  66.  
  67.         for(i=0; i<m; i++)
  68.         {
  69.             cin>>c>>d>>e;
  70.  
  71.             edge.push_back({e,{c,d}});
  72.         }
  73.  
  74.         sort(edge.begin(),edge.end());
  75.  
  76.         l=0;
  77.         k=INT_MAX;
  78.  
  79.         ///1st MST
  80.         for(auto dd:edge)
  81.         {
  82.             if(find_set(dd.second.second)!=find_set(dd.second.first))
  83.             {
  84.                 x[ {dd.second.first,dd.second.second}]=1;
  85.                 l+=dd.first;
  86.                 union_sets(dd.second.first,dd.second.second);
  87.             }
  88.         }
  89.  
  90.  
  91.         ///2nd best MST
  92.         for(auto dd:edge)
  93.         {
  94.             if(x[ {dd.second.first,dd.second.second}]==1)
  95.             {
  96.                 d=0;
  97.                 e=1;
  98.  
  99.                 make_set(n+2);
  100.  
  101.                 for(auto ee:edge)
  102.                 {
  103.                     if(find_set(ee.second.second)!=find_set(ee.second.first) && dd!=ee)
  104.                     {
  105.                         d+=ee.first;
  106.                         e++;
  107.                         union_sets(ee.second.first,ee.second.second);
  108.                     }
  109.  
  110.                     if(e>=n)
  111.                     {
  112.                         k=min(k,d);
  113.                         break;
  114.                     }
  115.                 }
  116.             }
  117.         }
  118.  
  119.         cout<<l<<" "<<k<<endl;
  120.     }
  121.  
  122.     return 0;
  123. }
  124.  
  125.  
  126. /*
  127.  
  128. for(i=0; i<m; i++)
  129. {
  130.     if(x[ {edge[i].second.first,edge[i].second.second}]==1)
  131.     {
  132.         e=1;
  133.         d=0;
  134.  
  135.         make_set(n+2);
  136.  
  137.         for(j=0; j<m; j++)
  138.         {
  139.             if(find_set(edge[j].second.second)!=find_set(edge[j].second.first) && i!=j)
  140.             {
  141.                 d+=edge[j].first;
  142.                 e++;
  143.                 union_sets(edge[j].second.first,edge[j].second.second);
  144.             }
  145.  
  146.             if(e>=n)
  147.             {
  148.                 k=min(k,d);
  149.                 break;
  150.             }
  151.         }
  152.     }
  153. }
  154.  
  155.  
  156. */
  157.  
  158.  
RAW Paste Data