Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int pr[10000];
- struct edge {
- int u, v, w;
- bool operator<(const edge& p) const
- {
- return w < p.w;
- }
- };
- vector<edge> e;
- int find(int r)
- {
- return (pr[r] == r) ? r : find(pr[r]);
- }
- int mst(int n)
- {
- sort(e.begin(), e.end());
- for (int i = 1; i <= n; i++)
- pr[i] = i;
- int count = 0, s = 0;
- for (int i = 0; i < (int)e.size(); i++) {
- int u = find(e[i].u);
- int v = find(e[i].v);
- if (u != v) {
- pr[u] = v;
- count++;
- s += e[i].w;
- if (count == n - 1)
- break;
- }
- }
- return s;
- }
- int main()
- {
- // READ("in");
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n, m;
- cin >> n >> m;
- for (int i = 1; i <= m; i++) {
- int u, v, w;
- cin >> u >> v >> w;
- edge get;
- get.u = u;
- get.v = v;
- get.w = w;
- e.push_back(get);
- }
- cout << mst(n) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement