Cod sursa(job #353901)

Utilizator crisojogcristian ojog crisojog Data 6 octombrie 2009 18:18:45
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<stdio.h>
#define mult 400010;
long part(long st, long dr)
{
	long i,j,m,pivot,aux;
	i=st-1;
	j=dr+1;
	m=(st+dr)/2;
	pivot=c[m];
	while(1)
	{
		do{++i;} while(c[i]<pivot);
		do{--j;} while(c[j]>pivot);
		if(i<j)
		{
			aux=c[i]; c[i]=c[j]; c[j]=aux;
			aux=a[i]; a[i]=a[j]; a[j]=aux;
			aux=b[i]; b[i]=b[j]; b[j]=aux;
		}
		else return j;
	}
}
void quicks(long st, long dr)
{
	long p;
	if(st<dr)
	{
		p=part(st,dr);
		quicks(st,p);
		quicks(p+1,dr);
	}
}

void read()
{
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;++i)
	{
		scanf("%ld%ld%ld",&a[i],&b[i],&c[i]);
	}
}
struct nod
{
	long info;
	nod *urm;
}; nod *t[mult];
void init()
{
	nod *p;
	for(i=1;i<=n;++i)
	{
		v[i]=i;
		p=new nod;
		p->info=i;
		p->urm=t[i];
	}
}
void rez()
{
	init();
	for(i=1;i<=m;++i)
	{
		if(v[a[i]]!=v[b[i]])
		{
			cost+=c[i];
			if(v[a[i]]<v[a[j]])
				
		}			
	}
	
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	read();
	quicks();
	rez();
}