fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. struct edge
  7. {
  8. ll x,y,w;
  9. bool operator<(const edge &p) const
  10. {
  11. return w<p.w;
  12. }
  13. } e[100005];
  14.  
  15. vector<edge>v;
  16.  
  17. ll pr[10005];
  18.  
  19. ll find(ll src)
  20. {
  21. if(pr[src]==src)
  22. return src;
  23. return pr[src]=find(pr[src]);
  24. }
  25.  
  26. ll mst(ll n)
  27. {
  28. sort(v.begin(),v.end());
  29. ll s=0,len=v.size(),cnt=0,i;
  30.  
  31. for(i=1; i<=n; i++)
  32. pr[i]=i;
  33. for(i=0; i<len; i++)
  34. {
  35. ll u=find(v[i].x);
  36. ll v1=find(v[i].y);
  37. if(u!=v1)
  38. {
  39. pr[u]=v1;
  40. cnt++;
  41. s+=v[i].w;
  42. if(cnt==n-1)
  43. break;
  44. }
  45. }
  46. return s;
  47. }
  48.  
  49. int main()
  50. {
  51. ll i,j,n,m,t,a,b,c;
  52. scanf("%lld%lld",&n,&m);
  53.  
  54. for(i=0; i<m; i++)
  55. {
  56. scanf("%lld%lld%lld",&a,&b,&c);
  57. edge g;
  58. g.x=a;
  59. g.y=b;
  60. g.w=c;
  61. v.push_back(g);
  62. }
  63. printf("%lld\n",mst(n));
  64. }
  65.  
Runtime error #stdin #stdout 4.64s 2096112KB
stdin
Standard input is empty
stdout
Standard output is empty