Pagini recente » Cod sursa (job #41542) | Cod sursa (job #1757643) | Cod sursa (job #1318114) | Cod sursa (job #1178826) | Cod sursa (job #761790)
Cod sursa(job #761790)
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 200005
int n,m,father[maxn] ;
struct muchie
{int x,y ;long long c1,c2 ;int ind ;} mc[maxn] ;
struct cmp
{
bool operator()(const muchie &a, const muchie &b)const
{
if(a.c1 < b.c1)
return 1;
else
if(a.c1 == b.c1)
{
if(a.c2 > b.c2)
return 1;
return 0;
}
else
return 0;
}
};
int tata(int nod)
{
if( nod == father[nod] )
return nod ;
father[nod] = tata( father[nod] ) ;
return father[nod] ;
}
int main()
{
freopen("lazy.in","r",stdin);
freopen("lazy.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d%lld%lld",&mc[i].x,&mc[i].y,&mc[i].c1,&mc[i].c2);
mc[i].ind = i ;
}
for(int i=1;i<=n;++i)
father[i] = i ;
sort(mc + 1 , mc + m + 1 , cmp() ) ;
for(int i=1;i<=m;++i)
{
if( tata( mc[i].x ) != tata( mc[i].y ) )
{
printf("%d\n",mc[i].ind);
father[ tata( mc[i].x ) ] = father[ tata( mc[i].y ) ] ;
}
}
return 0;
}