Pagini recente » Borderou de evaluare (job #1017349) | Cod sursa (job #1261370)
#include <fstream>
#include <algorithm>
#define MMAX 100002
#define NMAX 100002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m;
struct Muchie
{
int x, y;
double c;
};
Muchie G[MMAX];
int APM[NMAX];
int conex[MMAX];
double cost_APM;
int nrm;
void citire();
bool crit(Muchie, Muchie);
int main()
{
citire();
int i, j, c1, c2;
for(i = 1; nrm <= n-1 ; ++i)
{
if( conex[G[i].x] != conex[G[i].y] )
{
if( conex[G[i].x]<conex[G[i].y] )
{
c1 = conex[G[i].x];
c2 = conex[G[i].y];
}
else
{
c1 = conex[G[i].y];
c2 = conex[G[i].x];
}
APM[++nrm] = i;
cost_APM += G[i].c;
for(j = 1; j<=n; ++j)
if( conex[j] == c2)
conex[j] = c1;
}
}
fout<<cost_APM<<'\n'<<n-1<<'\n';
for(i = 1; i<=n-1; ++i)
fout<<G[APM[i]].y<<" "<<G[APM[i]].x<<'\n';
return 0;
}
void citire()
{
fin>>n>>m;
int i;
for(i = 1 ;i<=m; ++i)
fin>>G[i].x>>G[i].y >>G[i].c;
for(i = 1; i<=n; ++i)
conex[i] = i;
sort(G+1,G+m+1, crit);
/*
for(i = 1 ;i<=m; ++i)
fout<<G[i].x<<" "<<G[i].y<<" "<<G[i].c<<"\n";
*/
}
bool crit(Muchie a, Muchie b)
{
return (a.c < b.c);
}