Cod sursa(job #2329554)

Utilizator FredyLup Lucia Fredy Data 26 ianuarie 2019 22:18:47
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

#define limm 400010
#define limn 200010
int n,m;
struct tipmuchie {int x,y,cost;} muchie[limm];
struct solutie {int x,y;} sol[limm];
int costSol, nrmSol;
int dad[limn];

bool cmp(tipmuchie A, tipmuchie B)
{
    if(A.cost<B.cost) return 1;
    return 0;
}

int get_dad(int x)
{
    if(x!=dad[x])   dad[x] = get_dad(dad[x]);
    return dad[x];
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>muchie[i].x>>muchie[i].y>>muchie[i].cost;
    for(int i=1; i<=n; i++)
        dad[i] = i;
    sort(muchie+1, muchie+m+1, cmp);

    for(int i=1; i<=m; i++)
        if(get_dad(muchie[i].x) != get_dad(muchie[i].y))
        {
            dad[get_dad(muchie[i].x)] = get_dad(muchie[i].y);
            costSol += muchie[i].cost;
            sol[++nrmSol] = {muchie[i].x, muchie[i].y};
        }

    fout<<costSol<<'\n'<<nrmSol<<'\n';
    for(int i=1; i<=nrmSol; i++)
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';

    fin.close();
    fout.close();
    return 0;
}