Cod sursa(job #2669927)

Utilizator cristiemanuelstroe cristian emanuel cristiemanuel Data 8 noiembrie 2020 14:24:59
Problema Arbore partial de cost minim Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include  <fstream>
#include  <iostream>
#include  <vector>
#include  <algorithm>

using namespace std;

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

const int Nmax = 2e5 + 5;
int n, m, cnt;
vector<pair<int, int>>G[Nmax];
vector<pair<int, int>>G_min;
int T[Nmax];
struct muchie{
  int x, y, c;
}V[Nmax];
struct cmp{
  bool operator()(muchie x, muchie y)
  {
    return x.c < y.c;
  }
};

void read()
{
  in>>n>>m;
  for(int i = 1; i <= m; i++)
  {
    in>>V[i].x>>V[i].y>>V[i].c;
    G[V[i].x].push_back({V[i].y, V[i].c});
    G[V[i].y].push_back({V[i].x, V[i].c});
  }
}

void unire(int x, int y)
{
  T[x] = y;
  //G_min[cnt].push_back(y);
}

int radacina(int nod)
{
  int r = nod;
  while(T[r] != r)
    r = T[r];
/*  while(T[nod] != nod)
  {
    unire(r, nod);
    nod = T[nod];
  }*/
  return r;
}


void solve()
{
    int cost_min = 0;
    sort(V + 1, V + m + 1, cmp());
    for(int i = 1; i <= n; i++)
      T[i] = i;
    for(int i = 1; i <= m; i++)
    {
      int x = V[i].x,
          y = V[i].y,
          c = V[i].c;
      int X = radacina(x);
      int Y = radacina(y);
      if(X != Y)
        unire(X, Y), cost_min += c, cnt++, G_min.push_back({x,y});
    }
  out<<cost_min<<'\n'<<cnt<<'\n';
    for(auto it : G_min)
      out<<it.first<<' '<<it.second<<'\n';
}

int main()
{
  read();
  solve();
}