Pagini recente » Cod sursa (job #972970) | Cod sursa (job #2935650) | Cod sursa (job #2729957) | Cod sursa (job #2934819) | Cod sursa (job #761778)
Cod sursa(job #761778)
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 200001
struct muchie
{long long x,y,cost,profit,indice ;};
muchie mc[maxn] ;
int n,m,tata[maxn],sol[maxn] ;
bool cmp(muchie a, muchie b)
{
if( a.cost == b.cost )
return a.profit > b.profit ;
return a.cost < b.cost ;
}
int radacina(int a)
{
if( tata[a] == a )
return a ;
tata[a] = radacina ( tata[a] ) ;
return tata[a] ;
}
void adauga(int a,int b)
{
radacina ( a ) ;
tata[ radacina ( b ) ] = tata[ a ] ;
}
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%d%d",&mc[i].x,&mc[i].y,&mc[i].cost,&mc[i].profit);
mc[i].indice = i ;
}
sort( mc + 1 , mc + m + 1 , cmp ) ;
for(int i=1;i<=n;++i)
tata[i] = i ;
int nr = 0 ;
for(int i=1;i<=m;++i)
{
if( radacina ( mc[i].x ) != radacina ( mc[i].y ) )
{
adauga ( mc[i].x , mc[i].y ) ;
sol [ ++nr ] = mc[i].indice ;
}
}
sort( sol + 1 , sol + nr + 1 ) ;
for(int i=1;i<=nr;++i)
printf("%d\n",sol[i]);
return 0;
}