Opis glavnog rešenja

Očigledno je da se u zadatku traži ukupna cena grana koje pripadaju minimalnom povezujućem stablu. Minimalno povezujuće stablo možemo odrediti sortiranjem grana po ceni i spajanjem različitih komponenti. Za implementaciju ovog postupka ćemo pored ostalog koristiti unije (union find).

Prvo sve grane sortiramo po ceni rastuće. Nakon toga, redom prolazimo kroz sve grane i za oba čvora koja predstavljaju krajeve grane određujemo predstavnika grupe. Ukoliko oba čvora pripadaju istoj grupi, ne smemo dodati granu u stablo jer bismo time formirali ciklus (čime automatski gubimo svojstvo stabla). Ako grana spaja dva čvora koja pripadaju različitim grupama, izvršimo operaciju unije kako bismo čvorove spojili u istu grupu i dodajemo granu u stablo. Tokom dodavanja grana u stablo sumiramo njihove težine i na kraju dobijamo zbir cena svih grana koje su uključene u stablo.

Korak sortiranja grana je \(O(E \log E)\). Kasniji prolazak kroz sve grane je linerane složenosti u odnosu na njihov broj pa je ukupna složenost rešenja \(O(E \log E)\).

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

using namespace std;

struct Tacka {
   int x;
   int y;

   Tacka(int x, int y) {
      this->x = x;
      this->y = y;
   }
};

ostream& operator<<(ostream &out, const Tacka *t) {
   out << "[" << t->x << ", " << t->y << "]";
   return out;
}

unordered_map<Tacka *, Tacka *> roditelj;
unordered_map<Tacka *, int> rang;

void UF_inicijalizacija(const vector<Tacka *> &tacke)
{
   for (Tacka *t : tacke) {
      roditelj[t] = t;
      rang[t] = 0;
   }
}

Tacka *UF_nadji_grupu(Tacka *t)
{
    while (t != roditelj[t]) {
        roditelj[t] = roditelj[roditelj[t]];
        t = roditelj[t];
    }

    return t;
}

void UF_unija(Tacka *t1, Tacka *t2)
{
    Tacka *ft1 = UF_nadji_grupu(t1);
    Tacka *ft2 = UF_nadji_grupu(t2);

    if (ft1 == ft2) return;

    if (rang[ft1] < rang[ft2]) {
        roditelj[ft1] = ft2;
    } else if (rang[ft2] < rang[ft1]) {
        roditelj[ft2] = ft1;
    } else {
        roditelj[ft1] = ft2;
        rang[ft2]++;
    }
}

bool operator ==(Tacka t1, Tacka t2) {
   return t1.x == t2.x && t1.y == t2.y;
}

class Graph {

private:
   vector<pair<Tacka *, Tacka *>> grane;

   void sortitraj_grane() {
      std::sort(grane.begin(), grane.end(),
      [this](auto &g1, auto &g2){ return menhetn_rastojanje(g1.first, g1.second) < menhetn_rastojanje(g2.first, g2.second); });
   }

public:
   Graph() {
   }

   void dodaj_granu(Tacka *u, Tacka *v) {
      grane.push_back({u, v});
   }

   int menhetn_rastojanje(Tacka *t1, Tacka *t2) {
      return abs(t1->x - t2->x) + abs(t1->y - t2->y);
   }

   int izracunaj() {
      sortitraj_grane();

      int suma = 0;

      for (const auto &g : grane) {
         Tacka *t1 = g.first;
         Tacka *t2 = g.second;

         Tacka *grupa_t1 = UF_nadji_grupu(t1);
         Tacka *grupa_t2 = UF_nadji_grupu(t2);

         // Ako bismo dodali granu izmedju 2 cvora koja se vec nalaze u istoj grupi, dobili bismo ciklus
         if (grupa_t1 == grupa_t2) {
            continue;
         }

         UF_unija(t1, t2);

         suma += menhetn_rastojanje(g.first, g.second);
      }

      return suma;
   }
};

int main() {
   int n, x, y;

   cin >> n;

   Graph *G = new Graph();

   vector<Tacka *> tacke;

   for (int i = 0; i < n; i++) {
      cin >> x >> y;
      Tacka *t = new Tacka(x, y);
      tacke.push_back(t);
   }

   UF_inicijalizacija(tacke);

   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         G->dodaj_granu(tacke[i], tacke[j]);
      }
   }

   cout << G->izracunaj() << "\n";

   delete G;
   return 0;
}