# Cod sursa(job #1534842)

Utilizator Data 23 noiembrie 2015 23:53:07 Arbore partial de cost minim 0 cpp done Arhiva educationala 1.34 kb
``````#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int parent[200001], rank[200001];

int compress(int node) {
return (parent[node] == -1 ? node : parent[node] = compress(parent[node]));
}

int main() {
freopen("apm.in", "r", stdin);
freopen("apm.out", "w", stdout);

int n, m;
scanf("%d%d", &n, &m);

vector < pair < int, pair <int, int> > > edges;
for (int i = 0; i < m; ++i) {
int x, y, w;
scanf("%d %d %d", &x, &y, &w);
edges.push_back(make_pair(w, make_pair(x, y)));
}

sort(edges.begin(), edges.end());

for (int i = 0; i < n; ++i) {
parent[i] = - 1;
rank[i] = 1;
}

int ans = 0;
vector < pair <int, int> > v;
for (int i = 0; i < edges.size(); ++i) {
int rx = compress(edges[i].second.first);
int ry = compress(edges[i].second.second);
if (rx != ry) {
if (rank[rx] > rank[ry]) {
parent[ry] = rx;
rank[rx] += rank[ry];
} else {
parent[rx] = ry;
rank[ry] += rank[rx];
}
v.push_back(edges[i].second);
ans += edges[i].first;
}
}

printf("%d\n%d\n", ans, (int)v.size());

for (int i = 0; i < v.size(); ++i)
printf("%d %d\n", v[i].first, v[i].second);

return 0;
}
``````