Advertisement
Saleh127

SPOJ CSTREET / MST

Sep 27th, 2021
885
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.  
  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])
  43.         {
  44.             swap(a, b);
  45.         }
  46.  
  47.         parent[b] = a;
  48.  
  49.         if (rankk[a] == rankk[b])
  50.         {
  51.             rankk[a]++;
  52.         }
  53.         */
  54.     }
  55. }
  56.  
  57.  
  58. int main()
  59. {
  60.     ios_base::sync_with_stdio(0);
  61.     cin.tie(0);
  62.     cout.tie(0);
  63.  
  64.  
  65.     test
  66.     {
  67.  
  68.         ll p,n,m,i,l,c,d,e,f;
  69.  
  70.         cin>>p;
  71.         cin>>n;
  72.         cin>>m;
  73.  
  74.         c=0;
  75.  
  76.         edge.clear();
  77.         parent.resize(n+2);
  78.         rankk.resize(n+2);
  79.         make_set(n+2);
  80.  
  81.         for(i=0; i<m; i++)
  82.         {
  83.             cin>>d>>e>>f;
  84.             edge.push_back({f,{d,e}});
  85.         }
  86.  
  87.         sort(edge.begin(),edge.end());
  88.  
  89.  
  90.         for(auto dd:edge)
  91.         {
  92.             if(find_set(dd.second.second)!=find_set(dd.second.first))
  93.             {
  94.                 c+=dd.first;
  95.                 union_sets(dd.second.first,dd.second.second);
  96.             }
  97.         }
  98.  
  99.         cout<<c*p<<endl;
  100.     }
  101.  
  102.     return 0;
  103. }
  104.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement