nadogradnja

Jedna država unapređuje svoju strujnu mrežu kako bi spojila sve svoje gradove. Ukoliko je poznato između kojih gradova već postoje konekcije, treba odrediti koje konekcije treba dodati da svi gradovi postanu međusobno povezani, pritom treba minimizovati cenu održavanja koja je već poznata za stare konekcije, pa je dozvoljeno prestati sa održavanjem nekih starih konekcija. Za nove konekcije podrazumevati da je cena održavanja 0.

Opis ulaza

Sa standradnog ulaza unose se redom brojevi \(n\) i \(m\) (\(1 \leq n, m \leq 10^5\)), koji predstavljaju broj gradova i broj konekcija između njih. Zatim se unosi \(m\) već postojećih konekcija u formatu \(u\) \(v\) \(m\), gde su \(u\) i \(v\) gradovi između kojih postoji konekcija, a \(m\) cena održavanja.

Opis izlaza

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Prirodno je da modelujemo ovaj problem neusmerenim težinskim grafom, gde su čvorovi gradovi, grane konekcije, a težine cene održavanja.

Za početak, primetimo da, pošto ne moraju svi gradovi biti povezani na početku, može postojati više komponenti povezanosti u grafu. Zadatak se onda svodi na nalaženje minimalnog razapinjućeg stabla za svaku od komponenti povezanosti jer će nam to obezbediti minimalnu cenu održavanja u okviru svake od komponenti. Na kraju ostaje da povežemo svaku komponentu sa nekom od ostalih komponenti po jednom granom, pri čemu dodate grane ne utiču na krajnji rezultat jer im je cena održavanja 0.

Kako u implementaciji koirstimo Primov algoritam, složenost je \(O((|E| + |V|)\cdot \log|V|)\)

#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 Prim() {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> kljuc(broj_cvorova, INF);
        vector<bool> uMST(broj_cvorova, false);
        int ukupnaTezina = 0;

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

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

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

                    ukupnaTezina += kljuc[u];

                    for (auto &[v, tezina] : lista_suseda[u]) {
                        if (!uMST[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->Prim() << endl;

   delete G;
   return 0;
}