Pagini recente » Cod sursa (job #2067517) | Cod sursa (job #518920) | Cod sursa (job #2187753) | Cod sursa (job #2739147) | Cod sursa (job #795156)
Cod sursa(job #795156)
#include<fstream>
#include<algorithm>
#define N 200001
using namespace std;
ifstream f("lazy.in");
ofstream g("lazy.out");
int i,n,m,u,v,x[N],y[N],gr[N],rang[N],ind[N],c1[N],c2[N];
bool cmp(int a,int b)
{if(c1[a]<c1[b])
return 1;
else
if(c1[a]==c1[b])
if(c2[a]>c2[b])
return 1;
return 0;
}
int find(int x)
{if(gr[x]!=x)
gr[x]=find(gr[x]);
return gr[x];
}
int main()
{f>>n>>m;
for(i=1;i<=m;++i)
{f>>x[i]>>y[i]>>c1[i]>>c2[i];
ind[i]=i;
}
sort(ind+1,ind+m+1,cmp);
for(i=1;i<=n;++i)
{gr[i]=i;
rang[i]=i;
}
for(i=1;i<=m;++i)
{u=find(x[ind[i]]);
v=find (y[ind[i]]);
if(u!=v)
{if(rang[u]<rang[v])
gr[u]=v;
else
{rang[u]+=(rang[u]==rang[v]);
gr[v]=u;
}
g<<ind[i]<<'\n';
}}
return 0;
}