Cod sursa(job #766224)

Utilizator silviu982001Borsan Silviu silviu982001 Data 10 iulie 2012 17:08:21
Problema Lazy Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct much
{
    int st,fi,nb;
    long long ef,c;
};
const int N=200005;
int m,rx,ry,n,t[N];
bool used[N];
much v[N];
int compact(int nod)
{
    if(t[nod]==0) return nod;
    return (t[nod]=compact(t[nod]));
}
void read()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%lld%lld",&v[i].st,&v[i].fi,&v[i].ef,&v[i].c);
        v[i].nb=i;
    }
}
bool comp(const much &A,const much &B)
{
    if(A.ef<B.ef)
        return true;
    if(A.ef>B.ef)
        return false;
    return A.c>B.c;
}
int main()
{
    freopen("lazy.in","r",stdin);
    freopen("lazy.out","w",stdout);
    read();
    sort(v+1,v+m+1,comp);
    for(int i=1;i<=m;i++)
    {
        rx=compact(v[i].st);
        ry=compact(v[i].fi);
        if(rx!=ry)
        {
            t[ry]=rx;
            used[i]=true;
        }
    }
    for(int i=1;i<=m;i++)
        if(used[i])
            printf("%d\n",v[i].nb);
    return 0;
}