Saleh127

Light OJ 1041 / DSU - MST

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