Advertisement
Saleh127

Light OJ 1029 / MST - min & max

Nov 4th, 2021
834
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-04-19.21.47
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. vector<ll>parent,rankk;
  13.  
  14. vector<pair<ll,pair<ll,ll>>>edge;
  15.  
  16. bool cmp(pair<ll,pair<ll,ll>>&a, pair<ll,pair<ll,ll>>&b)
  17. {
  18.     return a.first>=b.first;
  19. }
  20.  
  21. void make_set(ll n)
  22. {
  23.     for(ll i=0; i<n; i++)
  24.     {
  25.         parent[i] = i;
  26.         rankk[i] = 0;
  27.     }
  28. }
  29.  
  30. int find_set(ll v)
  31. {
  32.     if (v == parent[v])
  33.     {
  34.         return v;
  35.     }
  36.     return parent[v] = find_set(parent[v]);
  37. }
  38.  
  39. void union_sets(ll a, ll b)
  40. {
  41.     a = find_set(a);
  42.     b = find_set(b);
  43.  
  44.     if (a != b)
  45.     {
  46.         if (rankk[a] < rankk[b])
  47.         {
  48.             swap(a, b);
  49.         }
  50.  
  51.         parent[b] = a;
  52.  
  53.         if (rankk[a] == rankk[b])
  54.         {
  55.             rankk[a]++;
  56.         }
  57.     }
  58. }
  59.  
  60.  
  61. int main()
  62. {
  63.     ios_base::sync_with_stdio(0);
  64.     cin.tie(0);
  65.     cout.tie(0);
  66.  
  67.     ll n,i,j,k,l,c,d,e,f;
  68.  
  69.     test
  70.     {
  71.         cin>>n;
  72.  
  73.         n++;
  74.  
  75.         l=c=0;
  76.  
  77.         edge.clear();
  78.         parent.resize(n);
  79.         rankk.resize(n);
  80.         make_set(n);
  81.  
  82.         while(1)
  83.         {
  84.             cin>>d>>e>>f;
  85.  
  86.             if(d+e+f==0) break;
  87.  
  88.             edge.push_back({f,{d,e}});
  89.         }
  90.  
  91.         sort(edge.begin(),edge.end());
  92.  
  93.  
  94.         for(auto dd:edge)
  95.         {
  96.             if(find_set(dd.second.second)!=find_set(dd.second.first))
  97.             {
  98.                 l+=dd.first;
  99.                 union_sets(dd.second.first,dd.second.second);
  100.             }
  101.         }
  102.  
  103.         sort(edge.begin(),edge.end(),cmp);
  104.  
  105.         parent.resize(n);
  106.         rankk.resize(n);
  107.         make_set(n);
  108.  
  109.  
  110.         for(auto dd:edge)
  111.         {
  112.             if(find_set(dd.second.second)!=find_set(dd.second.first))
  113.             {
  114.                 l+=dd.first;
  115.                 union_sets(dd.second.first,dd.second.second);
  116.             }
  117.         }
  118.  
  119.         cout<<"Case "<<cs<<": ";
  120.  
  121.         if(l%2==0) cout<<l/2<<nl;
  122.         else cout<<l<<"/"<<2<<nl;
  123.     }
  124.  
  125.     get_lost_idiot;
  126. }
  127.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement