Cod sursa(job #761790)

Utilizator matei_cChristescu Matei matei_c Data 27 iunie 2012 14:29:32
Problema Lazy Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<cstdio>
#include<algorithm>
using namespace std;

#define maxn 200005 

int n,m,father[maxn] ;

struct muchie
{int x,y ;long long c1,c2 ;int ind ;} mc[maxn] ;

struct cmp
{
	bool operator()(const muchie &a, const muchie &b)const
	{
		if(a.c1 < b.c1)
			return 1;
		else
			if(a.c1 == b.c1)
			{
				if(a.c2 > b.c2)
					return 1;
				return 0;
			}
		else
			return 0;
	}
};

int tata(int nod)
{
	if( nod == father[nod] )
		return nod ;
	father[nod] = tata( father[nod] ) ;
	return father[nod] ;
}

int main()
{
	
	freopen("lazy.in","r",stdin);
	freopen("lazy.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%lld%lld",&mc[i].x,&mc[i].y,&mc[i].c1,&mc[i].c2);
		mc[i].ind = i ;
	}
	
	for(int i=1;i<=n;++i)
		father[i] = i ;
	
	sort(mc + 1 , mc + m + 1 , cmp() ) ;
	
	for(int i=1;i<=m;++i)
	{
		if( tata( mc[i].x ) != tata( mc[i].y ) )
		{
			printf("%d\n",mc[i].ind);
			father[ tata( mc[i].x ) ] = father[ tata( mc[i].y ) ] ;
		}
	}
	
	return 0;

}