Pagini recente » Cod sursa (job #2007858) | Cod sursa (job #243548) | Cod sursa (job #1749506) | Cod sursa (job #529764) | Cod sursa (job #1307449)
#include<bits/stdc++.h>
using namespace std;
struct cell
{
int x,y,ind;
long long c1,c2;
};
ifstream fin("lazy.in");
ofstream fout("lazy.out");
const int NMAX=200005;
int n,m,father[NMAX];
cell a[NMAX];
bitset<NMAX>viz;
inline bool cmp(const cell A,const cell B)
{
if (A.c1==B.c1) return A.c2>B.c2;
return A.c1<B.c1;
}
inline void Union(int x,int y)
{
father[x]=y;
}
inline int Father(int x)
{
int y,z;
z=x;
while (x!=father[x]) x=father[x];
while (z!=father[x])
{
y=father[z];
father[z]=x;
z=y;
}
return x;
}
int main()
{
int i,aux,baux;
fin>>n>>m;
for (i=1;i<=n;i++) father[i]=i;
for (i=1;i<=m;i++)
{
a[i].ind=i;
fin>>a[i].x>>a[i].y>>a[i].c1>>a[i].c2;
}
sort(a+1,a+m+1,cmp);
for (i=1;i<=m;i++)
{
aux=Father(a[i].x);
baux=Father(a[i].y);
if (aux!=baux)
{
viz[a[i].ind]=1;
Union(aux,baux);
}
}
for (i=1;i<=m;i++)
if (viz[i]!=0) fout<<i<<"\n";
return 0;
}