fork download
copy 
  1. //Aulene
  2. //Kruskal was basically plagiarised from HackerEarth since I learnt it from there
  3.  
  4. #include<iostream>
  5. #include<fstream>
  6. #include<cstdio>
  7. #include<cstring>
  8. #include<cmath>
  9. #include<climits>
  10. #include<algorithm>
  11. #include<vector>
  12. #include<map>
  13. #include<queue>
  14. #include<stack>
  15. #include<set>
  16. #include<list>
  17.  
  18. using namespace std;
  19.  
  20. #define lli long long int
  21. #define mod 1000000007
  22. #define p push
  23. #define pb push_back
  24. #define mp make_pair
  25.  
  26. int a[2007][2007];
  27. bool vis[2007][2007];
  28. lli roots[2007];
  29. pair< int, pair <int, int > > p[2000007];
  30.  
  31. int root(int x)
  32. {
  33.     while(roots[x]!=x)
  34.             {
  35.                     roots[x]=roots[roots[x]];
  36.                     x=roots[x];
  37.             }
  38.     return x;
  39. }
  40.  
  41. lli kruskal(int n)
  42. {
  43.     int x, y, i, f, q;
  44.     lli cost, minCost=0;
  45.  
  46.     for(i=0; i<n; i++)
  47.         {
  48.             x=p[i].second.first;
  49.             y=p[i].second.second;
  50.             cost=p[i].first;
  51.  
  52.             f=root(x);
  53.             q=root(y);
  54.  
  55.             if(f!=q)
  56.                 {
  57.                         minCost+=cost;
  58.                         roots[f]=roots[q];
  59.                 }
  60.         }
  61.  
  62.     return minCost;
  63. }
  64.  
  65. int main()
  66.     {
  67.         lli n, i, j, x=0;
  68.         lli ans;
  69.  
  70.         cin >> n;
  71.  
  72.         for(i=1; i<=n; i++)
  73.             for(j=1; j<=n; j++)
  74.             scanf("%d", &a[i][j]);
  75.  
  76.         for(i=1; i<=n; i++)
  77.             roots[i]=i;
  78.  
  79.         for(i=1; i<=n; i++)
  80.             for(j=1; j<=n; j++)
  81.                 if(!vis[i][j] && i!=1 && j!=1 && i!=j) //ensure that 1 isn't present cuz its useless and stuff
  82.                     {
  83.                         p[x]=mp(a[i][j], mp(i, j));
  84.                         vis[i][j]=1;
  85.                         vis[j][i]=1;
  86.                         x++;
  87.                     }
  88.  
  89.         sort(p, p+x);
  90.         ans=kruskal(x);
  91.  
  92.         cout << ans << endl;
  93.  
  94.         return 0;
  95.     }
Time limit exceeded #stdin #stdout 5s 46592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jdpHOm
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!