Cod sursa(job #708214)

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

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

bool cmp(int A,int B) {
	return C[A]>C[B];
}
int DFS(int nod) {
	
	if(T[nod]!=nod)
		T[nod]=DFS(T[nod]);
	
	return T[nod];
	
}
void citire() {
	
	int i,C1,C2;
	ifstream in("lazy.in");
	
	in>>n>>m;
	
	for(i=1;i<=m;i++) {
		in>>X[i]>>Y[i]>>C1>>C2;
		C[i]=C1*(C2-1);
		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;
	
}