Cod sursa(job #2194158)

Utilizator andreibudoiAndrei Budoi andreibudoi Data 12 aprilie 2018 14:58:41
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("arbore.in");
ofstream g ("arbore.out");
int comp[200005];
struct muchie{
int x,y,c;
}v[400005];
bool mycmp(muchie a,muchie b)
{
    if (a.c<b.c) return 1;
    return 0;
}
int main()
{
    int n,m,a,b,i,cost=0,k=0,j;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,mycmp);
    for(i=1;i<=m;i++)
        comp[i]=i;
    for(i=0;i<=m&&k<n-1;i++)
    {
        if(comp[v[i].x]!=comp[v[i].y])
        {
            a=comp[v[i].x];
            b=comp[v[i].y];
            for(j=1;j<=n;j++)if(comp[j]==b)comp[j]=a;
            cost+=v[i].c;
            k++;
        }
    }
    cout<<cost;
    return 0;
}