Cod sursa(job #1720101)

Utilizator Bodo171Bogdan Pop Bodo171 Data 21 iunie 2016 13:37:30
Problema Lazy Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include<fstream>
#include<algorithm>
#include<bitset>
using namespace std;
const int nmax=200005;
int tt[nmax],rg[nmax],n,m,i,y,aux;
bitset<nmax> tru;
struct tip
{
    int a,b,idx;
    long long c,cs;
}v[nmax];
bool compare(tip x,tip y)
{
    if(x.c==y.c) return x.cs>y.cs;
    return x.c<y.c;
}
int finds(int x)
{
    y=x;
    while(x!=tt[x])
        x=tt[x];
    while(y!=x)
    {
        aux=tt[y];
        tt[y]=x;
        y=aux;
    }
    return x;
}
void unite(int a,int b)
{
    if(rg[a]>rg[b]) tt[b]=a;
    else tt[a]=b;
    if(rg[a]==rg[b]) rg[b]++;
}
int main()
{
    ifstream f("lazy.in");
    ofstream g("lazy.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].a>>v[i].b>>v[i].c>>v[i].cs;
        v[i].idx=i;
    }
    for(i=1;i<=n;i++)
    {
        tt[i]=i;
        rg[i]=1;
    }
    sort(v+1,v+n+1,compare);
    for(i=1;i<=m;i++)
    {
        if(finds(v[i].a)!=finds(v[i].b))
            {
                unite(finds(v[i].a),finds(v[i].b));
                tru[v[i].idx]=1;
            }
    }
    for(i=1;i<=m;i++)
        if(tru[i])
         g<<i<<'\n';
    return 0;
}