fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const long long MaxN = 5e2 + 5;
  6.  
  7. long long n,a[MaxN];
  8.  
  9. vector<pair<long long,pair<long long,long long>>> pr;
  10.  
  11. struct DSU
  12. {
  13.     long long lab[MaxN];
  14.     void init()
  15.     {
  16.         for (long long i=0; i<=n; i++)
  17.         {
  18.             lab[i]=-1;
  19.         }
  20.     }
  21.     long long get_root(long long u)
  22.     {
  23.         if(lab[u]<0) return u;
  24.         return lab[u]=get_root(lab[u]);
  25.     }
  26.     void unite(long long u , long long v)
  27.     {
  28.         long long x = get_root(u), y=get_root(v);
  29.         if(x==y)
  30.         {
  31.             return;
  32.         }
  33.         if(lab[x]>lab[y]) swap(x,y);
  34.         lab[x]+=lab[y];
  35.         lab[y]=x;
  36.         return;
  37.     }
  38.     bool check(long long u, long long v)
  39.     {
  40.         return get_root(u)==get_root(v);
  41.     }
  42.     long long get_size(long long u)
  43.     {
  44.         return -lab[get_root(u)];
  45.     }
  46. };
  47.  
  48. DSU dsu;
  49.  
  50. void input()
  51. {
  52.     cin>>n;
  53.  
  54.     for(long long i=1;i<=n;i++)
  55.     {
  56.         cin>>a[i];
  57.  
  58.         pr.push_back({a[i],{0,i}});
  59.     }
  60.  
  61.     for(long long i=1;i<=n;i++)
  62.     {
  63.         for(long long j=1;j<=n;j++)
  64.         {
  65.             long long val;
  66.             cin>>val;
  67.  
  68.             if(i!=j)
  69.             {
  70.                 pr.push_back({val,{i,j}});
  71.             }
  72.         }
  73.     }
  74. }
  75.  
  76. void solve()
  77. {
  78.     dsu.init();
  79.  
  80.     sort(pr.begin(),pr.end());
  81.  
  82.     long long ans=0;
  83.  
  84.     for(long long i=0;i<pr.size();i++)
  85.     {
  86.         long long w=pr[i].first;
  87.         long long u=pr[i].second.first;
  88.         long long v=pr[i].second.second;
  89.         if(u==v) continue;
  90.         if(!dsu.check(u,v))
  91.         {
  92.             dsu.unite(u,v);
  93.             ans+=w;
  94.         }
  95.     }
  96.  
  97.     cout<<ans;
  98. }
  99.  
  100. int main()
  101. {
  102.     ios_base::sync_with_stdio(0);
  103.     cin.tie(0);
  104.  
  105.     input();
  106.     solve();
  107. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OUQhzo
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!