Pagini recente » Cod sursa (job #1677875) | Cod sursa (job #2136398)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int n, m;
int t[200007], costmin, nrm;
struct Muchie
{
int x, y, cost, viz;
} a[400007];
void Citire()
{
int i;
fin >> n >> m;
for (i = 1; i <= m; i++)
fin >> a[i].x >> a[i].y >> a[i].cost;
}
inline bool Sortare(const Muchie A, const Muchie B)
{
return A.cost < B.cost;
}
int Find(int x)
{
int y, rad;
rad = x;
while (t[rad] != 0)
rad = t[rad];
while (x != rad)
{
y = t[x];
t[x] = rad;
x = y;
}
return rad;
}
void Union(int x, int y)
{
t[y] = x;
}
void Rezolvare()
{
int x, y, i;
costmin = 0;
nrm = n - 1;
sort (a + 1, a + m + 1, Sortare);
for (i = 1; i <= m && nrm != 0; i++)
{
x = Find(a[i].x);
y = Find(a[i].y);
if (x != y)
{
a[i].viz = 1;
Union(x, y);
costmin += a[i].cost;
nrm--;
}
}
}
void Afisare()
{
int i;
fout << costmin << "\n";
fout << n - 1 << "\n";
for (i = 1; i <= m; i++)
if (a[i].viz == 1)
fout << a[i].x << " " << a[i].y << "\n";
}
int main()
{
Citire();
Rezolvare();
Afisare();
fin.close();
fout.close();
return 0;
}