SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <string>
  4. #include <cmath>
  5. #include <cstdlib>
  6. #include <map>
  7. #include <set>
  8. #include <iostream>
  9. #include <vector>
  10. #include <algorithm>
  11. using namespace std;
  12.  
  13.  
  14. struct edge {
  15.     int from;
  16.     int to;
  17.     int weight;
  18.     bool inline friend operator < (edge x, edge y)
  19.     {
  20.         if (x.weight < y.weight)
  21.             return true;
  22.         return false;
  23.     }
  24. } edges[4500000];
  25. int parent[3001];
  26.  
  27. int findSet(int x)
  28. {
  29.     if (parent[x] == x)
  30.         return x;
  31.     return parent[x] = findSet(parent[x]);
  32. }
  33.  
  34. int main()
  35. {
  36.     int n,m;
  37.     cin >> n >> m;
  38.    
  39.     for (int i=0;i<m;i++)
  40.     {
  41.         int f,t,w;
  42.         cin >> f >> t >> w;
  43.         edges[i].from = f;
  44.         edges[i].to = t;
  45.         edges[i].weight = w;
  46.     }
  47.     sort(edges , edges + m);
  48.    
  49.     for (int i=1;i<=n;i++)
  50.         parent[i] = i;
  51.     int cnt = n, cur = 0;
  52.     int sum = 0;
  53.     while (cnt != 1)
  54.     {
  55.         if (findSet(edges[cur].from) != findSet(edges[cur].to))
  56.         {
  57.             parent[findSet(edges[cur].to)] = findSet(edges[cur].from);
  58.             sum += edges[cur].weight;
  59.             cnt--;
  60.         }
  61.         cur++;
  62.     }
  63.  
  64.     cout << sum;
  65. }
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