Cod sursa(job #3222071)

Utilizator TheAndreiEnache Andrei Alexandru TheAndrei Data 8 aprilie 2024 23:30:29
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>

#define nMax 200001
#define mMax 400001

using namespace std;

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

struct muchie{
    int x, y, cost;
}muchii[mMax];

int n, m, grupe[nMax], s;

void init(){
    for(int i=1;i<=n;i++)
        grupe[i]=i;
}

bool cmpMuchii(muchie a, muchie b){
    return a.cost<b.cost;
}

int find(int x) {
  if (grupe[x] == x)
    return x;
  return grupe[x] = find(grupe[x]);
}

void unite(int x, int y) {
  int setX, setY;

  setX = find(x);
  setY = find(y);
  if (setX != setY)
      grupe[setX] = setY;

}

int main()
{
    fin>>n>>m;
    init();
    for(int i=1;i<=m;i++)
        fin>>muchii[i].x>>muchii[i].y>>muchii[i].cost;
    std::sort(muchii+1, muchii+1+m, cmpMuchii);


    for (int i=1;i<=m;i++)
    if (find(muchii[i].x) != find(muchii[i].y)) {
      unite(muchii[i].x, muchii[i].y);
      s += muchii[i].cost;
    }

    fout<<s;

    return 0;
}