Pagini recente » Cod sursa (job #1877461) | Cod sursa (job #370531) | Cod sursa (job #1264851)
#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 200002
#define mmax 400002
FILE *f=fopen ("apm.in","r");
FILE *g=fopen ("apm.out","w");
struct muchie{
int x,y,cost;
}v[mmax];
int tata[nmax],rang[nmax],sol[nmax];
int cmp (muchie a, muchie b){
return a.cost<b.cost;
}
int find (int x){
int rad,aux;
for (rad=x;rad!=tata[rad];rad=tata[rad]);
while (x!=tata[x]){
aux=tata[x];
tata[x]=rad;
x=aux;
}
return rad;
}
void unite (int x, int y){
if (rang[x]>=rang[y]) tata[y]=x;
else tata[x]=y;
if (rang[x]==rang[y]) rang[x]++;
}
int main(){
int n,m,s=0,r=0;
fscanf (f,"%d%d",&n,&m);
for (int i=1;i<=n;++i){
tata[i]=i;
rang[i]=1;
}
for (int i=1;i<=m;++i) fscanf (f,"%d%d%d",&v[i].x,&v[i].y,&v[i].cost);
sort (v+1,v+m+1,cmp);
for (int i=1;i<=m && r<n;++i){
int a,b;
a=find (v[i].x);
b=find (v[i].y);
if (a!=b){
s+=v[i].cost;
sol[++r]=i;
unite (a,b);
}
}
fprintf (g,"%d\n%d\n",s,r);
for (int i=1;i<=r;++i) fprintf (g,"%d %d\n",v[sol[i]].x,v[sol[i]].y);
return 0;
}