Opis glavnog rešenja

Potrebno je da mreža na kraju bude povezana, a nove konekcije možemo dodavati bez dodatne cene održavanja. Zato nije potrebno plaćati održavanje svih postojećih konekcija. Dovoljno je da unutar svake postojeće komponente povezanosti zadržimo najjeftiniji skup konekcija koji povezuje sve gradove te komponente.

Za svaku komponentu postojećeg grafa treba pronaći minimalno povezujuće stablo. Nakon toga različite komponente možemo povezati novim konekcijama čija je cena \(0\), pa one ne menjaju ukupnu cenu održavanja.

Minimalno povezujuće stablo u svakoj komponenti određujemo Primovim algoritmom. Koristimo red sa prioritetom u kome se nalaze kandidati za sledeću granu najmanje cene. Kada prvi put uzmemo neki grad iz reda, dodajemo ga u stablo i njegovu cenu dodajemo na ukupan zbir. Zatim posmatramo sve njegove susede i, ako preko trenutne grane možemo jeftinije da ih povežemo sa stablom, ažuriramo njihovu cenu.

Pošto graf ne mora biti povezan, postupak pokrećemo iz svakog grada koji još nije dodat u neko stablo. Za početni grad svake komponente cena je \(0\), jer se za njega ne bira ulazna grana.

Složenost postupka je \(O(m \log n)\), zbog operacija nad redom sa prioritetom.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

class Graph {
private:
    int broj_cvorova; 
    vector<vector<pair<int, int>>> lista_suseda; 

public:
    Graph(int n) {
        this->broj_cvorova = n;
        lista_suseda.resize(n);
    }

    void dodaj_granu(int u, int v, int w) {
        lista_suseda[u].push_back(make_pair(v, w));
        lista_suseda[v].push_back(make_pair(u, w)); 
    }

    int izracunaj() {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> kljuc(broj_cvorova, INF);
        vector<bool> uStablu(broj_cvorova, false);
        int ukupnaTezina = 0;

        
        for (int start = 0; start < broj_cvorova; ++start) {
            if (!uStablu[start]) {
                pq.push(make_pair(0, start));
                kljuc[start] = 0;

                while (!pq.empty()) {
                    int u = pq.top().second;
                    pq.pop();

                    if (uStablu[u]) continue;
                    uStablu[u] = true;

                    ukupnaTezina += kljuc[u];

                    for (auto &[v, tezina] : lista_suseda[u]) {
                        if (!uStablu[v] && kljuc[v] > tezina) {
                            kljuc[v] = tezina;
                            pq.push(make_pair(kljuc[v], v));
                        }
                    }
                }
            }
        }
        return ukupnaTezina;
    }
};

int main() {

   int n, m;
   cin >> n >> m;
   Graph *G = new Graph(n);
   for (int i = 0; i < m; ++i) {
      int u, v, w;
      cin >> u >> v >> w;
      G->dodaj_granu(u-1, v-1, w); 
   }
   cout << G->izracunaj() << endl;

   delete G;
   return 0;
}