Pagini recente » Cod sursa (job #171833) | Cod sursa (job #2495555) | Cod sursa (job #1747091) | Cod sursa (job #375137) | Cod sursa (job #1452525)
#include <cstdio>
#include <vector>
#include <algorithm>
#define cost first
#define x second.first
#define y second.second
using namespace std;
const int Nmax = 200010;
const int Mmax = 400010;
int n , m , i , ans;
int T[Nmax] , rang[Nmax];
pair < int , pair < int , int > > edge[Mmax];
vector < pair < int , int > > ans_edges;
int multime(int node)
{
if (node != T[node])
T[node] = multime(T[node]);
return T[node];
}
void Union(int mult1 , int mult2)
{
if (rang[mult1] < rang[mult2])
T[mult1] = mult2;
else T[mult2] = mult1;
if (rang[mult1] == rang[mult2])
rang[mult1]++;
}
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d %d", &n, &m);
for (i = 1; i <= m; ++i)
scanf("%d %d %d", &edge[i].x, &edge[i].y, &edge[i].cost);
sort(edge + 1 , edge + m + 1);
for (i = 1; i <= n; ++i)
T[i] = i;
for (i = 1; i <= m; ++i)
{
int m1 = multime(edge[i].x); int m2 = multime(edge[i].y);
if (m1 != m2)
{
Union(m1 , m2);
ans += edge[i].cost;
ans_edges.push_back(edge[i].second);
}
}
printf("%d\n%d\n", ans , ans_edges.size());
for (i = 0; i < ans_edges.size(); ++i)
printf("%d %d\n", ans_edges[i].first, ans_edges[i].second);
return 0;
}