Opis glavnog rešenja

Zadatak se svodi na pronalaženje minimalnog povezujućeg stabla u neusmerenom težinskom grafu. Za to možemo koristiti jednostavan postupak sa sortiranjem grana.

Prvo sortiramo sve grane po ceni rastuće. Zatim prolazimo kroz sortirane grane i proveravamo da li krajevi trenutne grane pripadaju istoj komponenti povezanosti. Ako pripadaju istoj komponenti, dodavanjem te grane bismo napravili ciklus, pa je preskačemo. Ako pripadaju različitim komponentama, dodajemo granu u rešenje i spajamo te dve komponente union-find strukturom.

Na kraju, ako smo dodali tačno \(n - 1\) grana, dobili smo minimalno povezujuće stablo i ispisujemo njegovu cenu. U suprotnom graf nije povezan, pa nije moguće povezati sve gradove.

Sortiranje grana je složenosti \(O(m \log m)\), dok su union-find operacije praktično konstantne, pa je ukupna složenost \(O(m \log m)\).

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Grana {
   int u;
   int v;
   int cena;
};

vector<int> roditelj;
vector<int> rang;

void UF_inicijalizacija(int n)
{
   roditelj.resize(n);
   rang.assign(n, 0);

   for (int i = 0; i < n; i++) {
      roditelj[i] = i;
   }
}

int UF_nadji_grupu(int cvor)
{
   while (cvor != roditelj[cvor]) {
      roditelj[cvor] = roditelj[roditelj[cvor]];
      cvor = roditelj[cvor];
   }

   return cvor;
}

void UF_unija(int cvor1, int cvor2)
{
   int grupa1 = UF_nadji_grupu(cvor1);
   int grupa2 = UF_nadji_grupu(cvor2);

   if (grupa1 == grupa2) return;

   if (rang[grupa1] < rang[grupa2]) {
      roditelj[grupa1] = grupa2;
   } else if (rang[grupa2] < rang[grupa1]) {
      roditelj[grupa2] = grupa1;
   } else {
      roditelj[grupa1] = grupa2;
      rang[grupa2]++;
   }
}

class Graph {
private:
   int broj_cvorova;
   vector<Grana> grane;

   void sortiraj_grane()
   {
      sort(grane.begin(), grane.end(), [](const Grana &g1, const Grana &g2) {
         return g1.cena < g2.cena;
      });
   }

public:
   Graph(int n)
   {
      broj_cvorova = n;
   }

   void dodaj_granu(int u, int v, int cena)
   {
      grane.push_back({u, v, cena});
   }

   long long izracunaj()
   {
      sortiraj_grane();

      long long ukupna_cena = 0;
      int broj_dodatih_grana = 0;

      for (const Grana &grana : grane) {
         int grupa_u = UF_nadji_grupu(grana.u);
         int grupa_v = UF_nadji_grupu(grana.v);

         // Ako su krajevi grane vec u istoj grupi, dodavanje grane bi napravilo ciklus.
         if (grupa_u == grupa_v) {
            continue;
         }

         UF_unija(grana.u, grana.v);
         ukupna_cena += grana.cena;
         broj_dodatih_grana++;
      }

      if (broj_dodatih_grana != broj_cvorova - 1) {
         return -1;
      }

      return ukupna_cena;
   }
};

int main()
{
   int n, m;
   cin >> n >> m;

   Graph *G = new Graph(n);
   UF_inicijalizacija(n);

   for (int i = 0; i < m; i++) {
      int u, v, cena;
      cin >> u >> v >> cena;
      G->dodaj_granu(u - 1, v - 1, cena);
   }

   cout << G->izracunaj() << endl;

   delete G;
   return 0;
}