Pagini recente » Cod sursa (job #1044101) | Cod sursa (job #881589) | Cod sursa (job #1232167) | Cod sursa (job #157719) | Cod sursa (job #708225)
Cod sursa(job #708225)
#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;
}