Advertisement
Saleh127

Light OJ 1059 / DSU-MST

Nov 5th, 2021
953
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-05-23.00.33
  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. vector<pair<ll,pair<ll,ll>>>edge;
  14.  
  15.  
  16. void make_set(ll n)
  17. {
  18.     for(ll i=0; i<=n+2; i++)
  19.     {
  20.         parent[i] = i;
  21.         rankk[i] = 0;
  22.     }
  23. }
  24.  
  25. ll find_set(ll v)
  26. {
  27.     if (v == parent[v])
  28.     {
  29.         return v;
  30.     }
  31.     return parent[v] = find_set(parent[v]);
  32. }
  33.  
  34. void union_sets(ll a, ll b)
  35. {
  36.     a = find_set(a);
  37.     b = find_set(b);
  38.  
  39.     if (a != b)
  40.     {
  41.         if (rankk[a] < rankk[b])
  42.         {
  43.             swap(a, b);
  44.         }
  45.  
  46.         parent[b] = a;
  47.  
  48.         if (rankk[a] == rankk[b])
  49.         {
  50.             rankk[a]++;
  51.         }
  52.     }
  53. }
  54.  
  55.  
  56. int main()
  57. {
  58.     ios_base::sync_with_stdio(0);
  59.     cin.tie(0);
  60.     cout.tie(0);
  61.  
  62.     ll n,m,c,i,j,k,l;
  63.  
  64.     test
  65.     {
  66.         cin>>n>>m>>c;
  67.  
  68.         edge.clear();
  69.         parent.resize(n+5);
  70.         rankk.resize(n+5);
  71.         make_set(n);
  72.  
  73.  
  74.         for(i=0;i<m;i++)
  75.         {
  76.              cin>>j>>k>>l;
  77.  
  78.              if(l>=c) continue;
  79.  
  80.              edge.push_back({l,{j,k}});
  81.         }
  82.  
  83.         sort(edge.begin(),edge.end());
  84.  
  85.         l=0;
  86.         for(auto dd:edge)
  87.         {
  88.             if(find_set(dd.second.second)!=find_set(dd.second.first))
  89.             {
  90.                 l+=dd.first;
  91.                 union_sets(dd.second.first,dd.second.second);
  92.             }
  93.         }
  94.  
  95.         set<ll>airport;
  96.  
  97.         for(i=1;i<=n;i++)
  98.         {
  99.              airport.insert(find_set(i));
  100.         }
  101.  
  102.         l=l+ (airport.size())*c;
  103.  
  104.         cout<<"Case "<<cs<<": "<<l<<" "<<airport.size()<<nl;
  105.  
  106.     }
  107.  
  108.     get_lost_idiot;
  109. }
  110.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement