Cod sursa(job #1671465)

Utilizator Athena99Anghel Anca Athena99 Data 1 aprilie 2016 19:23:05
Problema Lazy Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#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;
}