# Cod sursa(job #541480)

Utilizator Data 25 februarie 2011 11:41:00 Lazy 0 cpp done Romanian Master in Mathematics and Sciences 2011, Ziua 1 1.16 kb
``````#include<cstdio>
#include<algorithm>

using namespace std;

#define Nmax 200001

struct muchie {
long long x, y, cost, profit, ind;
} V[Nmax];

long long N, M, T[Nmax], val, sol[Nmax*2];

long long cmp(muchie a, muchie b) {
if(a.cost!=b.cost)
return a.cost<b.cost;
else
return a.profit>b.profit;
}

long long get_root(long long x) {
while(T[x]!=x)
x=T[x];
return x;
}

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

long long i, j, a, b, c, d, k, root1, root2;
scanf("%lld %lld",&N,&M);
for(i=1; i<=M; i++) {
scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
V[i].x=a; V[i].y=b;
V[i].cost=b;
V[i].profit=d-(c*d);
V[i].ind=i;
T[i]=i;
}
sort(V+1,V+M+1,cmp);
for(k=1; k<=M && val<N-1; k++) {
i=V[k].x; j=V[k].y; c=V[k].cost;
root1=get_root(i);
root2=get_root(j);
if(root1==root2)
continue;
if(root1>root2)
T[root1]=T[root2];
else
T[root2]=T[root1];
sol[++val]=V[k].ind;
}

/*for(i=1; i<=M; i++)
printf("%lld %lld %lld %lld %lld\n",V[i].x,V[i].y,V[i].cost,V[i].profit,V[i].ind);*/

for(i=1; i<=val; i++)
printf("%lld\n",sol[i]);

return 0;
}``````