Cod sursa(job #1206720)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 10 iulie 2014 23:51:35
Problema Lazy Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define Nmax 200005

using namespace std;



struct elem{
    long long cost,profit;
    int a,b,poz;
};
class cmp{
public:
    bool operator()(const elem &e1,const elem &e2)const
    {
        if(e1.cost < e2.cost) return 1;
        if(e1.cost > e2.cost) return 0;
        return e1.profit < e2.profit;
    }
};
vector<elem> V;
int N,M,daddy[Nmax];

int whos_ur_daddy(int k)
{
    if(daddy[k] != k)
        daddy[k] = whos_ur_daddy(daddy[k]);
    return daddy[k];
}
void couple(int a,int b)
{
    daddy[daddy[a]] = daddy[b];
}

void read()
{
    scanf("%d%d",&N,&M);
    for(int i = 1; i <= N; ++i)
        daddy[i] = i;
    int a,b;
    long long c,d;
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d%d%lld%lld",&a,&b,&c,&d);
        elem e;
        e.a = a;
        e.b = b;
        e.cost = c;
        e.profit = d;
        e.poz = i;
        V.push_back(e);
    }
    sort(V.begin(),V.end(),cmp());
}

void solve()
{
    vector<int> sol;
    int x,y;
    for(int i = 0; i < M; ++i)
    {
        x = V[i].a;
        y = V[i].b;
        if(whos_ur_daddy(x) != whos_ur_daddy(y))
        {
            couple(x,y);
            sol.push_back(V[i].poz);
        }
    }
    sort(sol.begin(),sol.end());
    for(int i = 0; i <(int) sol.size(); ++i)
        printf("%d\n",sol[i]);
}

int main()
{
    freopen("lazy.in","r",stdin);
    freopen("lazy.out","w",stdout);

    read();
    solve();

    return 0;
}