Cod sursa(job #2039145)

Utilizator DavidLDavid Lauran DavidL Data 14 octombrie 2017 11:57:05
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");

struct muchie
{
    int u,v,c;
};

vector <muchie> M;
int n,m;
int p[200005];

int parinte(int nod
            {

            })

bool cmp(muchie a,muchie b)
{
    return a.c<b.c;
}

int main()
{
    fi>>n>>m;
    for (int i=1; i<=n; i++)
        p[i]=i;
    for (int i=1; i<=m; i++)
    {
        int a,b,cost; fi>>a>>b>>cost;
        M.push_back({a,b,cost});
    }
    sort(M+1,M+m+1);
    int muchiiAdd=0,rez=0;
    for (int i=1; i<=m; i++)
    {
        if (parinte(M[i].u)!=parinte(M[i].v))
        {
            rez+=M[i].c;
            muchiiAdd++;
            unite(M[i].u,M[i].v);
        }
        if (muchiiAdd==n-1)
            break;
    }
    fo<<rez;
    return 0;
}