Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <set>
- #include <utility>
- #include <algorithm>
- using namespace std;
- vector<long long> parent;
- vector<pair<long long, pair<long long, long long> > > graph;
- long long find_parent(long long node) {
- if (node != parent[node])
- parent[node] = find_parent(parent[node]);
- return parent[node];
- }
- int main() {
- long long N, M;
- cin >> N >> M;
- for (int i = 0; i <= N; i++)
- parent.push_back(i);
- for (long long i = 0; i < M; i++) {
- long long from, to, cost;
- cin >> from >> to >> cost;
- pair<long long, long long> edge(from, to);
- graph.push_back(pair<long long, pair<long long, long long> >(-cost, edge));
- }
- set<long long> nodes_visited;
- int visited_count = 0;
- long long cost = 0;
- sort(graph.begin(), graph.end());
- for (long long i = 0; i < graph.size() && nodes_visited.size() != N; i++) {
- long long p1, p2;
- p1 = find_parent(graph[i].second.first);
- p2 = find_parent(graph[i].second.second);
- if (p1 != p2) {
- cost += graph[i].first;
- visited_count++;
- parent[p1] = parent[p2];
- //for (int i = 1; i < parent.size(); i++) cout << parent[i] << " "; cout << "\n";
- }
- }
- if (visited_count != N - 1) cout << "-1" << "\n";
- else cout << -cost << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement