Advertisement
Guest User

Untitled

a guest
Sep 24th, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.21 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pi pair<int,pair<int,int>>
  5. pi ed[200009];
  6. ll parent[200009],edge;
  7. ll root(ll x)
  8. {
  9. if(parent[x]==x)
  10. {
  11. return x;
  12. }
  13. else
  14. {
  15. parent[x]=root(parent[x]);
  16. return parent[x];
  17. }
  18. }
  19. void un(ll a,ll b)
  20. {
  21. a=root(a);
  22. b=root(b);
  23. parent[a]=parent[b];
  24. }
  25. ll kruskal(pi p[])
  26. {
  27. ll i,x,y,cost,m=0;
  28. for(i=0;i<edge;i++)
  29. {
  30. x=p[i].second.first;
  31. y=p[i].second.second;
  32. cost=p[i].first;
  33. if(root(x)!=root(y))
  34. {
  35. m+=cost;
  36. un(x,y);
  37. }
  38. }
  39. return m;
  40. }
  41. void init()
  42. {
  43. for(int i=0;i<=200000;i++)
  44. parent[i]=i;
  45. }
  46. int main()
  47. {
  48. ll node,i,j,ans,org,u,v,c;
  49. while(scanf("%lld %lld",&node,&edge)==2)
  50. {
  51. org=0;
  52. ans=0;
  53. init();
  54. if(node==0 && edge==0)
  55. break;
  56. for(i=0;i<edge;i++)
  57. {
  58. cin>>u>>v>>c;
  59. org+=c;
  60. ed[i]=make_pair(c,make_pair(u,v));
  61. ed[i]=make_pair(c,make_pair(v,u));
  62. }
  63. sort(ed,ed+edge);
  64. ans=kruskal(ed);
  65. cout<<org-ans<<endl;
  66. }
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement