Advertisement
Guest User

Untitled

a guest
Dec 11th, 2016
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<vector>
  6. #include<algorithm>
  7. #define MAXN 200003
  8. using namespace std;
  9. struct edge
  10. {
  11. long u,v,w;
  12. bool operator < ( const edge& p ) const
  13. {
  14. return w < p.w;
  15. }
  16. };
  17.  
  18. long pr[MAXN];
  19. int find(long r)
  20. {
  21. if(pr[r]==r)
  22. return r;
  23. else
  24. return pr[r]=find(pr[r]);
  25. }
  26.  
  27. vector<edge>e;
  28. int mst(long n)
  29. {
  30. sort(e.begin(),e.end());
  31. long count=0,s=0;
  32. for(long i=0;i<(long)e.size();i++)
  33. {
  34. long u=find(e[i].u);
  35. long v=find(e[i].v);
  36. if(u!=v)
  37. {
  38. pr[u]=v;
  39. count++;
  40. s+=e[i].w;
  41.  
  42. if(count==n-1)
  43. break;
  44. }
  45. }
  46. return s;
  47. }
  48.  
  49. int main()
  50. {
  51. long n,m,sum;
  52. while(scanf("%ld%ld",&n,&m)==2)
  53. {
  54. if(!n && !m)
  55. break;
  56.  
  57. memset(pr,0,sizeof(pr));
  58. e.clear();
  59. sum=0;
  60. for(long i=0;i<m;i++)
  61. {
  62. long u,v,w;
  63. pr[i]=i;
  64. scanf("%ld%ld%ld",&u,&v,&w);
  65. edge get;
  66. get.u=u; get.v=v; get.w=w;
  67. sum=sum+w;
  68. e.push_back(get);
  69. }
  70.  
  71. long save=sum-mst(n);
  72. printf("%ld\n",save);
  73. }
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement