Untitled
unknown
c_cpp
3 years ago
1.3 kB
4
Indexable
#include <iostream> #include <vector> using namespace std; const int maxn = 1e5 + 10; int idx[maxn], sz[maxn]; int find_root(int x) { while(x != idx[x]) { idx[x] = idx[idx[x]]; x = idx[x]; } return x; } void unite_two_elements(int A, int B) { int root_a = find_root(A); int root_b = find_root(B); if(root_a != root_b) { if(sz[root_a] < sz[root_b]) { idx[root_a] = idx[root_b]; sz[root_b] += sz[root_a]; } else { idx[root_b] = idx[root_a]; sz[root_a] += sz[root_b]; } } } int main() { for(int i = 0; i < maxn; i++) { idx[i] = i; sz[i] = 1; } int n, m; cin >> n >> m; vector<pair<int, pair<int, int> > > v; for(int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; --a; --b; v.push_back(make_pair(c, make_pair(a, b))); } sort(v.begin(), v.end()); int result = 0; for(int i = 0; i < m; i++) { int c = v[i].first; int a = v[i].second.first; int b = v[i].second.second; if(find_root(a) != find_root(b)) { unite_two_elements(a, b); cout << a << " " << b << " " << c << endl; result += c; } } cout << result << endl; return 0; }
Editor is loading...