Cod sursa(job #3370670)

Utilizator Rizi_SanNen Ioana Madlena Rizi_San Data 26 octombrie 2026 18:25:18
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int NMAX = 200000;

int n, m;

vector<pair<int, pair<int, int>>>graf;
vector<pair<int, int>>apm;

int rad[NMAX+1];

int radacina(int nod)
{
    if (rad[nod] == nod)
        return nod;
    return rad[nod] = radacina(rad[nod]);
}

int cost_total;

int main()
{
    in>>n>>m;

    for (int i=1; i<=m; i++)
    {
        int cost, x, y;
        in>>x>>y>>cost;
        graf.push_back({cost, {x, y}});
        rad[i] = i;///radacina pt fiecare este el insusi initial
    }


    sort(graf.begin(), graf.end());

    /*
    for (int i=0; i<m; i++)
    {
        out<<graf[i].second.first<<" "<<graf[i].second.second<<" "<<graf[i].first<<endl;
    }*/

    for (int i=0; i<m; i++)
    {
        int x = graf[i].second.first;
        int y  = graf[i].second.second;
        int cost = graf[i].first;

        if (radacina(x)!=radacina(y))
        {
            cost_total+=cost;
            rad[radacina(x)] = radacina(y);
            apm.push_back({x, y});
        }


    }

    out<<cost_total<<"\n";
    out<<n-1<<"\n";

    for (int i=0; i<n-1; i++)
        out<<apm[i].first<<" "<<apm[i].second<<"\n";

    return 0;
}