Cod sursa(job #761774)

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

#define maxn 10001

struct muchie
{long long x,y,cost,profit,indice ;};

muchie mc[maxn] ;
int n,m,tata[maxn],sol[maxn] ;

bool cmp(muchie a, muchie b)
{
    if( a.cost == b.cost )
        return a.profit > b.profit ;
    return a.cost < b.cost ;
}

int radacina(int a)
{
    if( tata[a] == a )
        return a ;
    tata[a] = radacina ( tata[a] ) ;
    return tata[a] ;
}

void adauga(int a,int b)
{
    radacina ( a ) ;
    tata[ radacina ( b ) ] = tata[ a ] ;
}

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%d%d",&mc[i].x,&mc[i].y,&mc[i].cost,&mc[i].profit);
        mc[i].indice = i ;
    }
	
    sort( mc + 1 , mc + m + 1 , cmp ) ;
    
	for(int i=1;i<=n;++i)
        tata[i] = i ;
	
	int nr = 0 ;
    for(int i=1;i<=m;++i)
	{
        if( radacina ( mc[i].x ) != radacina ( mc[i].y ) )
		{
            adauga ( mc[i].x , mc[i].y ) ;
            sol [ ++nr ] = mc[i].indice ;
        }
    }
	
    sort( sol + 1 , sol + nr + 1 ) ;
	
    for(int i=1;i<=nr;++i)
        printf("%d\n",sol[i]);
    
	return 0;

}