Pagini recente » Cod sursa (job #545928) | Cod sursa (job #2380139) | Cod sursa (job #2808738) | Cod sursa (job #617239) | Cod sursa (job #1720102)
#include <iostream>
#include<fstream>
#include<algorithm>
#include<bitset>
using namespace std;
const int nmax=200005;
int tt[nmax],rg[nmax],n,m,i,y,aux;
bitset<nmax> tru;
struct tip
{
int a,b,idx;
long long c,cs;
}v[nmax];
bool compare(tip x,tip y)
{
if(x.c==y.c) return x.cs>y.cs;
return x.c<y.c;
}
int finds(int x)
{
y=x;
while(x!=tt[x])
x=tt[x];
while(y!=x)
{
aux=tt[y];
tt[y]=x;
y=aux;
}
return x;
}
void unite(int a,int b)
{
if(rg[a]>rg[b]) tt[b]=a;
else tt[a]=b;
if(rg[a]==rg[b]) rg[b]++;
}
int main()
{
ifstream f("lazy.in");
ofstream g("lazy.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>v[i].a>>v[i].b>>v[i].c>>v[i].cs;
v[i].idx=i;
}
for(i=1;i<=n;i++)
{
tt[i]=i;
rg[i]=1;
}
sort(v+1,v+m+1,compare);
for(i=1;i<=m;i++)
{
if(finds(v[i].a)!=finds(v[i].b))
{
unite(finds(v[i].a),finds(v[i].b));
tru[v[i].idx]=1;
}
}
for(i=1;i<=m;i++)
if(tru[i])
g<<i<<'\n';
return 0;
}