Pagini recente » Cod sursa (job #219027) | Cod sursa (job #921827) | Cod sursa (job #822377) | Cod sursa (job #2436293) | Cod sursa (job #1022168)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 200005
#define mmax 400005
using namespace std;
struct edge { int a, b, w; };
vector <edge> v;
int n, m, x, y, c, cost = 0, edges;
int w[nmax]; //padurea
bool check[mmax]; //muchiile luate
edge attrib(int a, int b, int w) {
edge temp;
temp.a = a; temp.b = b; temp.w = w;
return temp;
}
bool cmp(edge a, edge b) { return (a.w < b.w); }
int find(int x) {
if(w[x] < 0) return x;
w[x] = find(w[x]);
return w[x];
}
void join(int R, int T) {
if(w[R] < w[T]) w[R] += w[T], w[T] = R;
else w[T] += w[R], w[R] = T;
}
int main() {
ifstream f("apm.in");
ofstream g("apm.out");
f>>n>>m;
for(int i=1; i<=n; i++) w[i] = -1;
for(int i=1; i<=m; i++) {
f>>x>>y>>c;
v.push_back(attrib(x, y, c));
}
sort(v.begin(), v.end(), cmp);
for(int i=0; i<int(v.size()); i++) {
x = find(v[i].a);
y = find(v[i].b);
if(x != y) { //arbori diferiti
check[i] = true; //iau muchia
cost += v[i].w;
edges++;
join(x, y); //unesc arborii
}
}
g<<cost<<"\n"<<edges<<"\n";
for(int i=0; i<int(v.size()); i++)
if(check[i]) g<<v[i].a<<" "<<v[i].b<<"\n";
return 0;
}