SHARE
TWEET

Untitled

a guest May 19th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. const int MAXN = 1000;
  8.  
  9. struct Edge
  10. {
  11.     int from, to, price;
  12.     Edge( int f, int t, int p ) : from(f), to(t), price(p) {}
  13.     bool operator<( const Edge& e ) const
  14.     {
  15.         return price < e.price;
  16.     }
  17. };
  18.  
  19. int N, M, parent[MAXN], rankk[MAXN];
  20. vector <Edge> edges;
  21.  
  22. void input()
  23. {
  24.     scanf("%d %d", &N, &M);
  25.     int f, t, p;
  26.     for( int i = 0; i < M; i++ )
  27.     {
  28.         scanf("%d %d %d", &f, &t, &p);
  29.         edges.push_back(Edge(f, t, p));
  30.         parent[edges[i].from-1] = edges[i].from-1;
  31.         parent[edges[i].to-1] = edges[i].to-1;
  32.     }
  33. }
  34.  
  35. void union_trees( int from, int to )
  36. {
  37.     if( rankk[from] == rankk[to] )
  38.     {
  39.         parent[to] = from;
  40.         rankk[from]++;
  41.     }
  42.     else if( rankk[from] < rankk[to] )
  43.     {
  44.         parent[from] = to;
  45.     }
  46.     else
  47.     {
  48.         parent[to] = from;
  49.     }
  50. }
  51.  
  52. int find( int node )
  53. {
  54.     if( parent[node] == node )
  55.     {
  56.         return node;
  57.     }
  58.  
  59.     return parent[node] = find(parent[node]);
  60. }
  61.  
  62. void kruskal()
  63. {
  64.     sort(edges.begin(), edges.end());
  65.  
  66.     int i = 0, ans = 0, br = 0;
  67.     while( br < N-1 )
  68.     {
  69.         int p1 = find(edges[i].from);
  70.         int p2 = find(edges[i].to);
  71.         if( p1 != p2 )
  72.         {
  73.             union_trees(p1, p2);
  74.             br++;
  75.             ans += edges[i].price;
  76.         }
  77.         i++;
  78.     }
  79.     printf("%d\n", ans);
  80. }
  81.  
  82.  
  83. int main()
  84. {
  85.     input();
  86.     kruskal();
  87.  
  88.     return 0;
  89. }
  90. /**
  91.  
  92. 6 10
  93. 1 2 1
  94. 3 6 1
  95. 3 1 2
  96. 3 2 4
  97. 1 6 3
  98. 5 3 2
  99. 3 4 1
  100. 4 5 1
  101. 4 2 10
  102. 2 5 1
  103.  
  104. **/
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top