Cod sursa(job #2435751)

Utilizator AlexNeaguAlexandru AlexNeagu Data 4 iulie 2019 12:59:55
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct edge
{
    int weight, x, y;
};
vector < edge > E(400005);
vector < pair < int, int > > result;
int n, m, link[400005], rang[400005], total_weight = 0;
bool cmp(edge a, edge b)
{
    return a.weight < b.weight;
}
int Find(int node)
{
    for (;node != link[node]; node = link[node]);
    return node;
}
void unite (int x, int y)
{
    x = Find(x);
    y = Find(y);
    if (rang[x] < rang[y]) swap(x, y);
    rang[x] += rang[y];
    link[y] = x;
}

bool same(int x, int y)
{
    return Find(x) == Find(y);
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    cin >> E[i].x >> E[i].y >> E[i].weight;
    sort(E.begin(), E.end(), cmp);
    for (int i = 1; i <= n; i++) link[i] = i, rang[i] = 1;
    for (int i = 0; i < E.size(); i++)
    if(!same(E[i].x, E[i].y))
    {
        unite(E[i].x, E[i].y);
        result.push_back({E[i].x, E[i].y});
        total_weight += E[i].weight;
    }
    cout << total_weight << "\n" << result.size() << "\n";
    for (auto it : result) cout << it.first << " " << it.second << "\n";
    return 0;
}