Pagini recente » Cod sursa (job #3279669) | Cod sursa (job #3161459) | Cod sursa (job #2454276) | Cod sursa (job #806644) | Cod sursa (job #2173276)
#include <iostream>
#include <fstream>
#include <algorithm>
#define DM 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, a, b, c, dad[DM], cost_total, dim;
struct muchie {int x, y, cost;};
muchie g[DM], arb[DM];
bool cmp(muchie a, muchie b)
{
return a.cost < b.cost;
}
int root(int nod)
{
if(dad[nod] == nod)
return nod;
return dad[nod] = root(dad[nod]);
}
void unite(int x, int y)
{
dad[root(x)] = root(y);
}
int main ()
{
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
fin >> a >> b >> c;
g[i] = {a, b, c};
}
sort(g + 1, g + m + 1, cmp);
for(int i = 1; i <= n; i++)
dad[i] = i;
for(int i = 1; i <= m; i++)
{
a = g[i].x;
b = g[i].y;
c = g[i].cost;
if(root(a) != root(b))
{
unite(a, b);
arb[++dim] = {a, b, c}; // aici nu ne pasa de cost oricum
cost_total += c;
}
}
fout << cost_total << '\n';
fout << dim << '\n';
for(int i = 1; i <= dim; i++)
fout << arb[i].x << ' ' << arb[i].y << '\n';
return 0;
}