fork(1) download 
  1. /// kruskal by muoii
  2. /// vn.spoj.com/problems/QBMST/
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define tag "spoj"
  6. #define maxn 1007
  7. #define maxc 207
  8. #define oo 1000000007
  9. #define mid ((l+r)>>1)
  10. #define meset(a,x) memset(a,x,sizeof(a))
  11. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  12. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  13. int n,m;
  14. struct edge{
  15.     int depa,dest,weigh;
  16.     bool operator < (const edge &e) { return weigh<e.weigh; };
  17. };
  18. vector<edge> E;
  19.  
  20. struct dsu{
  21.  
  22.     int siz;
  23.     vector<int> par;
  24.  
  25.     dsu(const int &n): siz(n), par(n+2,0) {};
  26.  
  27.     int root(const int &v)
  28.     {
  29.         return par[v]<=0?v:par[v]=root(par[v]);
  30.     }
  31.  
  32.     bool unite(int x,int y)
  33.     {
  34.         if((x=root(x))==(y=root(y))) return false;
  35.  
  36.         if(par[x]>par[y]) par[y]=x;
  37.         else par[y]-=(par[x]==par[y]),par[x]=y;
  38.  
  39.         return true;
  40.     }
  41. };
  42.  
  43. int main()
  44. {
  45.     #ifdef dmdd
  46.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  47.     #endif // dmdd
  48.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  49.  
  50.     cin>>n>>m;
  51.  
  52.     int u,v,w;
  53.     while(m-->0) cin>>u>>v>>w,E.push_back({u,v,w});
  54.  
  55.     sort(E.begin(),E.end());
  56.  
  57.     int ans=0;
  58.     dsu mst(n);
  59.  
  60.     for(const edge &e: E) ans+=mst.unite(e.depa,e.dest)?e.weigh:0;
  61.  
  62.     cout<<ans;
  63.  
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
6 9
1 2 1
1 3 1
2 4 1
2 3 2
2 5 1
3 5 1
3 6 1
4 5 2
5 6 2
stdout 
5
https://ideone.com/Kmhhrq
language:
C++14 (gcc 8.3)
created:
6 years 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!