Cod sursa(job #732789)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 10 aprilie 2012 22:43:31
Problema Lazy Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<fstream>
#include<vector>
#define dim 200020
#include<algorithm>
using namespace std;


ifstream f("lazy.in");
ofstream g("lazy.out");
int T[dim],I[dim],n,m,a,b,k,i;;
struct cub {
	
	int x,y,i;
	long long  c,p;
}
v[dim];
vector<int>s;
int tata(int x){
	if(T[x]!=x)
		T[x]=tata(T[x]);
	return T[x];
}
int  cmp (cub a,cub b) {
	
	if(a.c==b.c)
		return a.p>b.p;
	else
		return a.c<b.c;
	
}
int main () {
	
	f>>n>>m;
	
	for(i=1;i<=m;i++){
		f>>v[i].x>>v[i].y>>v[i].c>>v[i].p;
		T[i]=v[i].i=i;
	}
	
	sort(v+1,v+1+m,cmp);
	
	for(i=1;i<=m;i++){
		
		a=tata(v[v[i].i].x);
		b=tata(v[v[i].i].y);
		
		if(a!=b){
			T[a]=b;
			s.push_back(v[i].i);
		}
		
		
	}
	sort(s.begin(),s.end());
	for(i=0;i<s.size();i++)
		g<<s[i]<<"\n";
	return 0;
}