Pagini recente » Cod sursa (job #624807) | Cod sursa (job #2959374) | Cod sursa (job #101732) | Cod sursa (job #560934) | Cod sursa (job #1671465)
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("lazy.in");
ofstream fout("lazy.out");
const int nmax= 200000;
int r[nmax+1], edge[nmax+1];
struct str {
int x, y, d, p;
} v[nmax+1];
int root( int x ) {
if ( r[x]!=x )
return r[x]= root(r[x]);
return r[x];
}
bool comp( int i, int j ) {
if ( v[i].d==v[j].d )
return v[i].p>v[j].d;
return v[i].d<v[j].d;
}
int main( ) {
int n, m;
fin>>n>>m;
for ( int i= 1; i<=m; ++i ) {
fin>>v[i].x>>v[i].y>>v[i].d>>v[i].p;
edge[i]= i;
}
for ( int i= 1; i<=n; ++i ) {
r[i]= i;
}
sort( edge+1, edge+m+1, comp );
for ( int i= 1; i<=m; ++i ) {
int x= root(v[edge[i]].x), y= root(v[edge[i]].y);
if ( x!=y ) {
r[y]= r[x];
fout<<edge[i]<<"\n";
}
}
return 0;
}