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

Top