tacke_u_ravni

Neka je dato \(n\) tačaka u ravni određeno svojim koordinatama. Potrebno je formirati izlomljenu liniju minimalne dužine koja spaja sve ove tačke. Za određivanje udaljenosti dve tačke koristiti Menhetn rastojanje.

Opis ulaza

Sa standarnog ulaza se unosi broj tačaka \(n\). Nakon toga se za svaku od njih unose po 2 vrednosti koje predstavljaju koordinate u ravni.

Opis izlaza

Na standardni izlaz ispisati jednu vrednost koja predstavlja minimalnu dužinu izlomljene krive koja spaja sve ove tačke.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Očigledno je da se u zadatku traži ukupna cena grana koje pripadaju minimalnom povezujućem stablu. Za određivanje minimalnog povezujućeg stabla možemo koristiti Kruskalov algoritam. Za implementaciju ovog algoritma ć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 MCST 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 MCST. Tokom dodavanja grana u stablo sumiramo njihove težine i na kraju dobijamo zbir cena svih grana koje su uključene u MCST.

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:
   int broj_cvorova;
   unordered_map<Tacka *, vector<pair<Tacka *, int>>> lista_suseda;
   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, int w) {
      lista_suseda[u].push_back({v, w});
      lista_suseda[v].push_back({u, w});
      grane.push_back({u, v});
   }

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

   int kruskal() {
      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], G->menhetn_rastojanje(tacke[i], tacke[j]));
      }
   }

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

   delete G;
   return 0;
}