Pagini recente » Cod sursa (job #3176204) | Cod sursa (job #2811286) | Cod sursa (job #2064695) | Cod sursa (job #2274626) | Cod sursa (job #544121)
Cod sursa(job #544121)
#include<fstream>
#include<algorithm>
#define DIM 200004
using namespace std;
struct lazy{
int x,y,ord;
long long cost;
long long profit;};
lazy v[DIM];
int t[DIM],n,m,nr,sol[DIM];
int find(int x);
int comp(lazy a,lazy b);
int main()
{
ifstream fin("lazy.in");
ofstream fout("lazy.out");
fin>>n>>m;
int i;
for(i=1;i<=m;i++)
fin>>v[i].x>>v[i].y>>v[i].cost>>v[i].profit,v[i].ord=i;
sort(v+1,v+m+1,comp);
for(i=1;i<=m;i++)
{
int X,Y;
X=find(v[i].x);
Y=find(v[i].y);
if(X!=Y)
{
t[Y]=X;
sol[++nr]=v[i].ord;
}
}
for(i=1;i<=nr;i++)
fout<<sol[i]<<"\n";
return 0;
}
int find(int x)
{
int found=x;
while(t[found]!=0)
found=t[found];
int aux;
while(t[x]!=0)
{
aux=x;
x=t[x];
t[aux]=found;
}
return found;
}
int comp(lazy a,lazy b)
{
if(a.cost>b.cost)
return 0;
else
if(a.cost==b.cost)
if(a.profit<b.profit)
return 0;
return 1;
}