Cod sursa(job #708225)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 6 martie 2012 16:28:52
Problema Lazy Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAx 200200
using namespace std;

vector <int> Sol;
int n,m,X[NMAx],Y[NMAx],V[NMAx],T[NMAx];
long long Cost[NMAx],Profit[NMAx];

bool cmp(int A,int B) {
	if(Cost[A]==Cost[B])
		return Profit[A]>Profit[B];
	return Cost[A]<Cost[B];
}
int DFS(int nod) {
	
	if(T[nod]!=nod)
		T[nod]=DFS(T[nod]);
	
	return T[nod];
	
}
void citire() {
	
	int i;
	ifstream in("lazy.in");
	
	in>>n>>m;
	
	for(i=1;i<=m;i++) {
		in>>X[i]>>Y[i]>>Cost[i]>>Profit[i];
		T[i]=V[i]=i;
		}
	
	in.close();
	
}
void afis() {
	
	ofstream out("lazy.out");
	
	for(int i=0;i<Sol.size();i++)
		out<<Sol[i]<<'\n';
	
	out.close();
	
}
int main() {
	
	int i,A,B;
	
	citire();
	
	sort(V+1,V+m+1,cmp);
	
	for(i=1;i<=m;i++) {
		
		A=DFS(X[V[i]]);
		B=DFS(Y[V[i]]);
		
		if(A!=B) {
			T[A]=B;
			Sol.push_back(V[i]);
			}
		
		}
	
	sort(Sol.begin(),Sol.end());
	
	afis();
	
	return 0;
	
}