Cod sursa(job #567184)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 29 martie 2011 19:57:18
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<algorithm>

using namespace std;

#define Nmax 262144

struct muchie {
	int i, j, poz;
	long long efort, profit;
} G[Nmax];
int N, M, T[Nmax], sol[Nmax];

ifstream f("lazy.in");
ofstream g("lazy.out");

inline int get_root(int x) {
	while(T[x]!=x)
		x=T[x];
	return x;
}

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

int main() {
	int i, j, k, root1, root2;
	
	f>>N>>M;
	for(i=1; i<=M; i++) {
		f>>G[i].i>>G[i].j>>G[i].efort>>G[i].profit;
		G[i].poz=i;
	}
	sort(G+1,G+M+1,cmp);
	for(i=1; i<=N; i++)
		T[i]=i;
	for(k=1; k<=M; k++) {
		i=G[k].i; j=G[k].j;
		root1=get_root(i);
		root2=get_root(j);
		if(root1==root2)
			continue;
		sol[++sol[0]]=G[k].poz;
		if(root1>root2)
			T[root1]=T[root2];
		else
			T[root2]=T[root1];
	}
	
	for(i=1; i<=sol[0]; i++)
		g<<sol[i]<<"\n";
	
	f.close(); g.close();
	
	return 0;
}