Pagini recente » Cod sursa (job #1571970) | Cod sursa (job #1364118) | Cod sursa (job #3214487) | Cod sursa (job #2709256) | Cod sursa (job #545147)
Cod sursa(job #545147)
#include<algorithm>
#include<vector>
using namespace std;
#define N_MAX 200005
#define ll long long
#define INF 1LL*1<<62
int n,m,x,y,i,j;
ll co,pr;
struct muchie
{
int x,y,i;
ll cost,profit;
muchie()
{
}
muchie(const int &x,const int &y,const ll &cost,const ll &profit,const int &i)
{
this->x=x;
this->y=y;
this->cost=cost;
this->profit=profit;
this->i=i;
}
};
muchie muchii[N_MAX];
int tata[N_MAX],grad[N_MAX];
int ind[N_MAX],nrInd;
inline bool cmp(const muchie &a,const muchie &b)
{
return a.cost<b.cost||a.cost==b.cost&&a.profit>b.profit;
}
int getRad(int nod)
{
int rad,aux;
for(rad=nod;rad!=tata[rad];rad=tata[rad]);
for(;nod!=tata[nod];nod=tata[nod])
{
aux=tata[nod];
tata[nod]=rad;
nod=aux;
}
return rad;
}
void uneste(int X,int Y)
{
if(grad[X]>=grad[y])
{
grad[X]++;
tata[Y]=X;
}
else
{
grad[Y]++;
tata[X]=Y;
}
}
int main()
{
freopen("lazy.in","r",stdin);
freopen("lazy.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%lld%lld",&x,&y,&co,&pr);
muchii[i]=muchie(x,y,co,pr,i);
}
sort(muchii+1,muchii+m+1,cmp);
for(i=1;i<=n;i++)
tata[i]=i,grad[i]=1;
int X,Y;
for(i=1;i<=m;i++)
{
X=getRad(muchii[i].x);
Y=getRad(muchii[i].y);
if(X!=Y)
{
uneste(X,Y);
ind[++nrInd]=muchii[i].i;
}
}
for(i=1;i<=nrInd;i++)
printf("%d\n",ind[i]);
return 0;
}