Pagini recente » Cod sursa (job #860359) | Cod sursa (job #1879853)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,s,nr;
struct muchie{
int x;
int y;
int c;
}v[400001],aux;
struct mte{
int val;
struct mte *urm;
}*l[200001],*actual;
int mt[200001], sol[200001];
void qs(int st, int dr){
int i=st,j=dr;
int x=v[i+(j-i)/2].c;
while(i<=j){
while(i<dr && v[i].c<x)
++i;
while(j>st && v[j].c>x)
--j;
if(i<=j){
aux=v[i];
v[i]=v[j];
v[j]=aux;
++i;
--j;
}
}
if(st<j)
qs(st,j);
if(i<dr)
qs(i,dr);
}
void kruskal(){
for(int i=1;i<=n;i++)
mt[i]=i;//initializez toate nodurile cu prorpria lor multime
for(int i=1;i<=n;++i){
actual=new mte;
actual->val=i;
actual->urm=l[i];
l[i]=actual;
}
for(int i=1;i<=m && nr<n-1;++i)
if(mt[v[i].x]!=mt[v[i].y]){
int mn,mx;
if(mt[v[i].x]<mt[v[i].y])
mn=mt[v[i].x],mx=mt[v[i].y];
else
mn=mt[v[i].y],mx=mt[v[i].x];
actual=l[mx];
while(actual->urm!=NULL){
mt[actual->val]=mn;
actual=actual->urm;
}
mt[actual->val]=mn;
actual->urm=l[mn];
l[mn]=l[mx];
l[mx]=NULL;
++nr;
s+=v[i].c;
sol[nr]=i;
}
}
int main()
{
in>>n>>m;
for(int i=1;i<=m;++i)
in>>v[i].x>>v[i].y>>v[i].c;
qs(1,m);//sortare
kruskal();
out<<s<<"\n"<<nr<<"\n";
for(int i=1;i<=nr;++i)
out<<v[sol[i]].y<<" "<<v[sol[i]].x<<"\n";
return 0;
}