Untitled
unknown
plain_text
a year ago
1.4 kB
3
Indexable
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define endl "\n" const double PI = 3.14159265358979; const ll INF = 1e9 + 7; const ll MOD = 1e9 + 7; const ll nax = 2505; const int LOG = 25; vector<int> par, sz; int getParent(int x) { return x == par[x] ? x : par[x] = getParent(par[x]); } void mergeGroups(int x, int y) { x = getParent(x); y = getParent(y); if (x == y) { return; } if (sz[x] < sz[y]) { par[x] = y; sz[y] += sz[x]; } else { par[y] = x; sz[x] += sz[y]; } } void solve() { int n, m; cin >> n >> m; par.assign(n + 1, 0); sz.assign(n + 1, 1); for (int i = 1; i <= n; i++) { par[i] = i; } vector<pair<int, pair<int, int> > > edges; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges.push_back({w, {u, v}}); } sort(edges.begin(), edges.end()); ll ans = 0; for (auto &edge: edges) { int w = edge.first; int u = edge.second.first; int v = edge.second.second; if (getParent(u) != getParent(v)) { mergeGroups(u, v); ans += w; } } cout << ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // int t; cin >> t; while(t--) solve(); return 0; }
Editor is loading...
Leave a Comment