Pagini recente » Cod sursa (job #2149525) | Cod sursa (job #2500403) | Cod sursa (job #1661495) | Cod sursa (job #3202129) | Cod sursa (job #1646663)
#include <algorithm>
#include <fstream>
#define NMax 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{
int x,y,c;
}G[NMax];
int n,m,Rx,Ry,cost,muchii;
int r[NMax],sol[NMax],rang[NMax];
int cmp(muchie x,muchie y){
return (x.c < y.c);
}
int root(int x){
while(r[x])
x = r[x];
return x;
}
void kruskal(){
for(int i = 1; i <= m; ++i){
rang[i] = 1;
}
for(int i = 1; i <= m && muchii < n - 1; ++i){
Rx = root(G[i].x);
Ry = root(G[i].y);
if(Rx != Ry){
sol[++muchii] = i;
cost += G[i].c;
if(rang[Rx] > rang[Ry]){
rang[Rx] += rang[Ry];
r[Ry] = Rx;
}else{
rang[Ry] += rang[Rx];
r[Rx] = Ry;
}
}
}
}
int main()
{
f >> n >> m;
for(int i = 1; i <= m; ++i){
f >> G[i].x >> G[i].y >> G[i].c;
}
sort(G + 1, G + 1 + m,cmp);
kruskal();
g << cost <<"\n" << n - 1 <<"\n";
for(int i = 1; i < n; ++i){
g << G[sol[i]].x <<" " << G[sol[i]].y <<"\n";
}
return 0;
}