• API
• FAQ
• Tools
• Archive
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.
Top