Cod sursa(job #544121)

Utilizator bora_marianBora marian bora_marian Data 1 martie 2011 08:36:20
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
#include<algorithm>
#define DIM 200004
using namespace std;
struct lazy{
	int x,y,ord;
	long long cost;
	long long profit;};
lazy v[DIM];
int t[DIM],n,m,nr,sol[DIM];
int find(int x);
int comp(lazy a,lazy b);
int main()
{
	ifstream fin("lazy.in");
	ofstream fout("lazy.out");
	fin>>n>>m;
	int i;
	for(i=1;i<=m;i++)
	   fin>>v[i].x>>v[i].y>>v[i].cost>>v[i].profit,v[i].ord=i;
	sort(v+1,v+m+1,comp);
	for(i=1;i<=m;i++)
	{
		int X,Y;
		X=find(v[i].x);
		Y=find(v[i].y);
		if(X!=Y)
		{
			t[Y]=X;
			sol[++nr]=v[i].ord;
		}
	}
	for(i=1;i<=nr;i++)
	   fout<<sol[i]<<"\n";
	return 0;
}
int find(int x)
{
	int found=x;
	while(t[found]!=0)
	     found=t[found];
	int aux;
	while(t[x]!=0)
	{
		aux=x;
		x=t[x];
		t[aux]=found;
	}
	return found;
}
int comp(lazy a,lazy b)
{
	if(a.cost>b.cost)
	  return 0;
	else
	  if(a.cost==b.cost)
	    if(a.profit<b.profit)
	       return 0;
	return 1;
}