Pagini recente » Cod sursa (job #451815) | Cod sursa (job #795812) | Statistici iaru briana (harciogul02) | Cod sursa (job #1275673) | Cod sursa (job #1206722)
#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 200005
using namespace std;
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()
{
scanf("%d%d",&N,&M);
for(int i = 1; i <= N; ++i)
daddy[i] = i;
int a,b;
long long c,d;
for(int i = 1; i <= M; ++i)
{
scanf("%d%d%lld%lld",&a,&b,&c,&d);
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;
}