Pagini recente » Cod sursa (job #1481884) | Cod sursa (job #2078450) | Cod sursa (job #187632) | Cod sursa (job #300494) | Cod sursa (job #1206729)
#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 200005
#define DIM 666013
using namespace std;
char buffer[DIM];
int poz = DIM - 1;
void scan(long long &A)
{
int sgn = 1;
A = 0;
while( ('0' > buffer[poz] || buffer[poz] > '9') && buffer[poz] != '-')
if(++poz == DIM) fread(buffer,1,DIM,stdin),poz = 0;
while( '0' <= buffer[poz] && buffer[poz] <= '9' || buffer[poz] == '-')
{
if(buffer[poz] == '-')
sgn *= -1;
else
A = A * 10 + buffer[poz] - 48;
if(++poz == DIM)
fread(buffer,1,DIM,stdin),poz = 0;
}
}
struct elem{
long long cost,profit;
int a,b,poz;
};
class cmp{
public:
bool operator()(const elem &e1,const elem &e2)const
{
if(e1.cost == e2.cost)
return e1.profit > e2.profit;
return e1.cost < e2.cost;
}
};
vector<elem> V;
int N,M,daddy[Nmax];
int whos_ur_daddy(int k)
{
if(daddy[k] != k)
daddy[k] = whos_ur_daddy(daddy[k]);
return daddy[k];
}
void couple(int a,int b)
{
daddy[daddy[a]] = daddy[b];
}
void read()
{
long long aux;
scan(aux);N = aux;
scan(aux);M = aux;
for(int i = 1; i <= N; ++i)
daddy[i] = i;
int a,b;
long long c,d;
for(int i = 1; i <= M; ++i)
{
scan(aux); a = aux;
scan(aux); b = aux;
scan(aux); c = aux;
scan(aux); d = aux;
elem e;
e.a = a;
e.b = b;
e.cost = c;
e.profit = d;
e.poz = i;
V.push_back(e);
}
sort(V.begin(),V.end(),cmp());
}
void solve()
{
vector<int> sol;
int x,y;
for(int i = 0; i < M; ++i)
{
x = V[i].a;
y = V[i].b;
if(whos_ur_daddy(x) != whos_ur_daddy(y))
{
couple(x,y);
sol.push_back(V[i].poz);
}
}
sort(sol.begin(),sol.end());
for(int i = 0; i <(int) sol.size(); ++i)
printf("%d\n",sol[i]);
}
int main()
{
freopen("lazy.in","r",stdin);
freopen("lazy.out","w",stdout);
read();
solve();
return 0;
}