Pagini recente » Cod sursa (job #189752) | Cod sursa (job #860030) | Cod sursa (job #495581) | Cod sursa (job #1705072)
# include <fstream>
# include <algorithm>
# include <vector>
using namespace std;
const int mmax=400001;
const int nmax=200001;
ifstream f("apm.in");
ofstream g("apm.out");
int grup[nmax], x[mmax], y[mmax], c[mmax], n, m, ind[mmax],ind_muchii_selectate[nmax];
bool comp(int i, int j)
{
return c[i] < c[j];
}
int FindSet(int i)
{
if (grup[i] == i) return i;
grup[i] = FindSet(grup[i]);
return grup[i];
}
void Union(int i, int j)
{
grup[FindSet(i)] = FindSet(j);
}
int main()
{
int i;
f >> n >> m;
for (i = 1; i <= m; i++)
{
f >> x[i] >> y[i] >> c[i];
ind[i] = i;
}
for (i = 1; i <= n; i++)
grup[i] = i;
sort(ind + 1, ind + m + 1, comp);
int suma = 0, K = 0;
for (i = 1; i <= m; i++)
{
if (FindSet(x[ind[i]]) != FindSet(y[ind[i]]))
{
suma += c[ind[i]];
Union(x[ind[i]], y[ind[i]]);
ind_muchii_selectate[++K] = ind[i];
}
}
g << suma << "\n";
g << n - 1 << "\n";
for (i = 1; i <= n - 1; i++)
g << x[ind_muchii_selectate[i]] << " " << y[ind_muchii_selectate[i]] << "\n";
return 0;
}