Advertisement
Saleh127

Light OJ 1040 / DFS - MST

Nov 4th, 2021
1,043
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.  
  17. bool cmp(pair<ll,pair<ll,ll>>&a, pair<ll,pair<ll,ll>>&b)
  18. {
  19.     return a.first>=b.first;
  20. }
  21.  
  22. void make_set(ll n)
  23. {
  24.     for(ll i=0; i<=n+2; i++)
  25.     {
  26.         parent[i] = i;
  27.         rankk[i] = 0;
  28.         v[i]=0;
  29.         g[i].clear();
  30.     }
  31. }
  32.  
  33. ll dfs(ll in)
  34. {
  35.     v[in]=1;
  36.     cnt++;
  37.     for(auto d:g[in])
  38.     {
  39.         if(v[d]==0)
  40.         {
  41.             dfs(d);
  42.         }
  43.     }
  44.     return cnt;
  45. }
  46.  
  47. ll find_set(ll v)
  48. {
  49.     if (v == parent[v])
  50.     {
  51.         return v;
  52.     }
  53.     return parent[v] = find_set(parent[v]);
  54. }
  55.  
  56. void union_sets(ll a, ll b)
  57. {
  58.     a = find_set(a);
  59.     b = find_set(b);
  60.  
  61.     if (a != b)
  62.     {
  63.         if (rankk[a] < rankk[b])
  64.         {
  65.             swap(a, b);
  66.         }
  67.  
  68.         parent[b] = a;
  69.  
  70.         if (rankk[a] == rankk[b])
  71.         {
  72.             rankk[a]++;
  73.         }
  74.     }
  75. }
  76.  
  77.  
  78. int main()
  79. {
  80.     ios_base::sync_with_stdio(0);
  81.     cin.tie(0);
  82.     cout.tie(0);
  83.  
  84.     ll n,i,j,k,l;
  85.  
  86.     test
  87.     {
  88.         cin>>n;
  89.  
  90.         l=cnt=0;
  91.  
  92.         edge.clear();
  93.         parent.resize(n+5);
  94.         rankk.resize(n+5);
  95.         make_set(n);
  96.  
  97.         for(i=0; i<n; i++)
  98.         {
  99.             for(j=0; j<n; j++)
  100.             {
  101.                 cin>>k;
  102.                 if(k!=0)
  103.                 {
  104.                     l+=k;
  105.                     edge.push_back({k,{i,j}});
  106.                     g[i].push_back(j);
  107.                     g[j].push_back(i);
  108.                 }
  109.             }
  110.         }
  111.  
  112.         cout<<"Case "<<cs<<": ";
  113.  
  114.         if(dfs(1ll)!=n) cout<<-1<<nl;
  115.         else
  116.         {
  117.             sort(edge.begin(),edge.end());
  118.  
  119.             k=0;
  120.             for(auto dd:edge)
  121.             {
  122.                 if(find_set(dd.second.second)!=find_set(dd.second.first))
  123.                 {
  124.                     l-=dd.first;
  125.                     union_sets(dd.second.first,dd.second.second);
  126.                 }
  127.             }
  128.             cout<<l<<nl;
  129.         }
  130.     }
  131.  
  132.     get_lost_idiot;
  133. }
  134.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement