Pagini recente » Cod sursa (job #2339058) | Cod sursa (job #2517079) | Cod sursa (job #2812189) | Cod sursa (job #393555) | Cod sursa (job #567184)
Cod sursa(job #567184)
#include<fstream>
#include<algorithm>
using namespace std;
#define Nmax 262144
struct muchie {
int i, j, poz;
long long efort, profit;
} G[Nmax];
int N, M, T[Nmax], sol[Nmax];
ifstream f("lazy.in");
ofstream g("lazy.out");
inline int get_root(int x) {
while(T[x]!=x)
x=T[x];
return x;
}
int cmp(muchie a, muchie b) {
if(a.efort==b.efort)
return a.profit > b.profit;
return a.efort < b.efort;
}
int main() {
int i, j, k, root1, root2;
f>>N>>M;
for(i=1; i<=M; i++) {
f>>G[i].i>>G[i].j>>G[i].efort>>G[i].profit;
G[i].poz=i;
}
sort(G+1,G+M+1,cmp);
for(i=1; i<=N; i++)
T[i]=i;
for(k=1; k<=M; k++) {
i=G[k].i; j=G[k].j;
root1=get_root(i);
root2=get_root(j);
if(root1==root2)
continue;
sol[++sol[0]]=G[k].poz;
if(root1>root2)
T[root1]=T[root2];
else
T[root2]=T[root1];
}
for(i=1; i<=sol[0]; i++)
g<<sol[i]<<"\n";
f.close(); g.close();
return 0;
}