Cod sursa(job #545147)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 2 martie 2011 19:42:53
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<algorithm>
#include<vector>

using namespace std;
#define N_MAX 200005
#define ll long long
#define INF 1LL*1<<62

int n,m,x,y,i,j;
ll co,pr;

struct muchie
{
	int x,y,i;
	ll cost,profit;
	
	muchie()
	{
	}
	
	muchie(const int &x,const int &y,const ll &cost,const ll &profit,const int &i)
	{
		this->x=x;
		this->y=y;
		this->cost=cost;
		this->profit=profit;
		this->i=i;
	}
};

muchie muchii[N_MAX];
int tata[N_MAX],grad[N_MAX];
int ind[N_MAX],nrInd;

inline bool cmp(const muchie &a,const muchie &b)
{
	return a.cost<b.cost||a.cost==b.cost&&a.profit>b.profit;
}

int getRad(int nod)
{
	int rad,aux;
	for(rad=nod;rad!=tata[rad];rad=tata[rad]);
	
	for(;nod!=tata[nod];nod=tata[nod])
	{
		aux=tata[nod];
		tata[nod]=rad;
		nod=aux;
	}
	
	return rad;
}

void uneste(int X,int Y)
{
	if(grad[X]>=grad[y])
	{
		grad[X]++;
		tata[Y]=X;
	}
	else
	{
		grad[Y]++;
		tata[X]=Y;
	}
}

int main()
{
	freopen("lazy.in","r",stdin);
	freopen("lazy.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%lld%lld",&x,&y,&co,&pr);
		muchii[i]=muchie(x,y,co,pr,i);
	}
	
	sort(muchii+1,muchii+m+1,cmp);
	
	for(i=1;i<=n;i++)
		tata[i]=i,grad[i]=1;
	
	int X,Y;
	
	for(i=1;i<=m;i++)
	{
		X=getRad(muchii[i].x);
		Y=getRad(muchii[i].y);
		if(X!=Y)
		{
			uneste(X,Y);
			ind[++nrInd]=muchii[i].i;
		}
	}
	
	for(i=1;i<=nrInd;i++)
		printf("%d\n",ind[i]);
	
	
	return 0;
}