Cod sursa(job #3041590)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 31 martie 2023 19:08:00
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

#define cin fin
#define cout fout

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

const int NMAX=2e5+5;

int t[NMAX];
int p[NMAX];

struct elem{
    int x;
    int y;
    int c;
}apm[NMAX];

bool cmp(int a,int b)
{
    return apm[a].c<apm[b].c;
}

int root(int x)
{
    if(x==t[x])
        return x;
    return t[x]=root(t[x]);
}

void solve(int x,int y)
{
    t[root(y)]=root(x);
}

vector<elem>v;

int main()
{
    int n,m,i,j;
    long long s=0;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        t[i]=i;
    for(i=1;i<=m;i++)
    {
        cin>>apm[i].x>>apm[i].y>>apm[i].c;
        p[i]=i;
    }
    sort(p+1,p+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        if(root(apm[p[i]].x)!=root(apm[p[i]].y))
        {
            solve(apm[p[i]].x,apm[p[i]].y);
            v.push_back(apm[p[i]]);
            s+=apm[p[i]].c;
        }
    }
    cout<<s<<"\n"<<v.size()<<"\n";
    for(auto i:v)
        cout<<i.x<<" "<<i.y<<"\n";
    return 0;
}