Cod sursa(job #3369919)

Utilizator JenJenCristache Ion JenJen Data 22 octombrie 2026 14:50:41
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin ("apm.in");
ofstream cout ("apm.out");

#define NMAX 200005
struct Muchie
{
    int u, v, cost;

    bool operator <(const Muchie& other) const
    {
        return cost < other.cost;
    }
};

int n, m, u, v, cost;

vector <Muchie> muchii;
vector <Muchie> rez;
int tata[NMAX];

void init()
{
    for (int i = 1; i <= n; i++)
    {
        tata[i] = i;
    }
}

int find(int n)
{
    if (tata[n] == n) return n;

    return tata[n] = find(tata[n]);
}

void unite(int a, int b)
{
    int dad_a = find(a);
    int dad_b = find(b);

    if (dad_a != dad_b) tata[dad_a] = dad_b;
}

long long costt;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v >> cost;
        muchii.push_back({u, v, cost});
    }

    init();
    sort(muchii.begin(), muchii.end());


    for (int i = 0; i < m && rez.size() < n - 1; i++)
    {
        Muchie curent = muchii[i];
        if (find(curent.u) != find(curent.v))
        {
            unite(curent.u, curent.v);
            rez.push_back(curent);
            costt += curent.cost;
        }
    }

    cout << costt << '\n';
    cout << rez.size() << '\n';
    for (int i = 0; i < rez.size(); i++)
    {
        cout << rez[i].u << " " << rez[i].v << '\n';
    }
    return 0;
}