Cod sursa(job #1264851)

Utilizator BLz0rDospra Cristian BLz0r Data 16 noiembrie 2014 13:31:43
Problema Arbore partial de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#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;
}