Pagini recente » Cod sursa (job #1074346) | Cod sursa (job #2787508) | Cod sursa (job #2731990) | Cod sursa (job #259651) | Cod sursa (job #2652766)
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("lazy.in");
ofstream fout("lazy.out");
long long m, el, i, f[200002],c,a,b,j,auxa,auxb ,nr;
long long sum;
pair <pair <long long, long long> , pair< int, pair <int, int > > > v[400002];
int z[400002], h[400002];
int calc(int nod)
{
int aux=nod, a;
while(f[nod]>0)
nod=f[nod];
while(f[aux]>0)
{
a=aux;
aux=f[aux];
f[a]=aux;
}
return nod;
}
int main(){
fin>>el>>m;
for(i=1;i<=el;i++)
f[i]=-1;
for(i=1;i<=m;i++)
{
fin>>v[i].second.first>>v[i].second.second.first>>v[i].first.first>>v[i].first.second;
v[i].first.second=-v[i].first.second;
v[i].second.second.second=i;
}
sort(v+1, v+1+m);
for(i=1;i<=m;i++)
{
a=v[i].second.first;
b=v[i].second.second.first;
auxa=calc(a);
auxb=calc(b);
if(auxa!=auxb)
{
if(f[auxa]<f[auxb])
{
f[auxa]+=f[auxb];
f[auxb]=auxa;
}
else
{
f[auxb]+=f[auxa];
f[auxa]=auxb;
}
nr++;
z[nr]=v[i].second.second.second;
}
}
for(i=1;i<=nr;i++)
fout<<z[i]<<"\n";
fin.close();
fout.close();
return 0;
}