Cod sursa(job #2444743)

Utilizator vladth11Vlad Haivas vladth11 Data 1 august 2019 12:19:04
Problema Lazy Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("lazy.in");
ofstream cout("lazy.out");
struct muchie{
    int a,b;
    long long cost,profit;
    bool operator < (muchie const &a)const{
         if(a.cost != cost){
            return (cost < a.cost);
         }else{
            return (a.profit < profit);
         }
    }
}v[200001];
int arbore[200001];
int c[200001];
int radacina(int x){
    if(c[x] == x){
        return x;
    }
    c[x] = radacina(c[x]);
    return c[x];
}
void uneste(int a,int b){
    c[radacina(a)] = radacina(b);
}
int main()
{
    int n,m,i;
    cin >> n >> m;
    for(i = 1;i <= n;i++){
        c[i] = i;
    }
    for(i = 1;i <= m;i++){
        cin >> v[i].a >> v[i].b >> v[i].cost >> v[i].profit;
    }
    sort(v + 1,v + m + 1);

    int cnt = 0;
    for(i = 1;i <= m;i++){
        if(radacina(v[i].a) != radacina(v[i].b)){
            cout << i << "\n";
            uneste(v[i].a,v[i].b);
        }
    }

    return 0;
}