Pagini recente » Cod sursa (job #2873565) | Cod sursa (job #360315) | Cod sursa (job #2519611) | Cod sursa (job #1021761) | Cod sursa (job #1261359)
#include <fstream>
#include <algorithm>
#define NMAX 200001
#define MMAX 400001
using namespace std;
ifstream fin("kruskal.in");
ofstream fout("kruskal.out");
struct Muchie {int x, y; double cost;};
Muchie g[MMAX];
int n, m;
double cost_apm;
int apm[NMAX]; //retin indicii celor n-1 muchii selectate
int conex[NMAX];
void citire();
int compara(Muchie, Muchie);
void kruskal();
void afisare();
int main()
{
citire();
sort(g, g+m, compara);
kruskal();
afisare();
return 0;
}
void citire()
{
int i;
fin>>n>>m;
for (i=0; i<m; ++i)
fin>>g[i].x>>g[i].y>>g[i].cost;
for(i=1; i<=n; i++)
conex[i]=i;
}
int compara(Muchie a, Muchie b)
{
return a.cost<b.cost;
}
void kruskal()
{
int i, j, maxim, minim;
int nrm=0; //nr de muchii selectate
for(i=0; nrm<n-1 ; i++)
{
if(conex[g[i].x]!=conex[g[i].y])
{
apm[++nrm]=i;
cost_apm=cost_apm+g[i].cost;
if(conex[g[i].x]>conex[g[i].y])
{
minim=conex[g[i].y];
maxim=conex[g[i].x];
}
else
{
minim=conex[g[i].x];
maxim=conex[g[i].y];
}
for(j=1; j<=n; j++)
if( conex[j]==maxim)
conex[j]=minim;
}
}
}
void afisare()
{
int i;
fout<<cost_apm<<'\n'<<n-1<<'\n';
for(i=1; i<=n-1; i++)
fout<<g[apm[i]].x<<' '<<g[apm[i]].y<<'\n';
}