U planinskoj oblasti nalazi se \(n\) sela. Svako selo treba da dobije signal.
Signal se može obezbediti na dva načina:
Poznato je \(m\) mogućih kablova. Za svaki kabl poznata su dva sela koja povezuje i cena postavljanja tog kabla.
Potrebno je odrediti minimalnu cenu tako da svako selo dobije signal.
Sa standardnog ulaza unose se brojevi \(n\) i \(m\) (\(1 \leq n \leq 10^5\), \(0 \leq m \leq 2 \cdot 10^5\)).
U narednom redu unosi se \(n\) celih brojeva \(a_1, a_2, \ldots, a_n\), gde je \(a_i\) cena izgradnje repetitora u selu \(i\).
U narednih \(m\) redova unose se po tri cela broja \(u\), \(v\) i \(c\), što znači da je moguće postaviti kabl između sela \(u\) i \(v\) po ceni \(c\).
Sela su numerisana od \(1\) do \(n\).
Ispisati minimalnu ukupnu cenu potrebnu da sva sela dobiju signal.
5 6 7 4 6 8 5 1 2 3 1 3 4 2 3 2 2 4 7 3 5 3 4 5 2
14
Jedno optimalno rešenje je da se izgradi repetitor u selu 2 po ceni 4, a zatim postave kablovi između sela 2 i 3, 3 i 5, 5 i 4, kao i 1 i 2. Ukupna cena je \(4 + 2 + 3 + 2 + 3 = 14\).
Na prvi pogled deluje da treba posebno odlučivati u kojim selima gradimo repetitore, a koja sela povezujemo kablovima. Međutim, problem možemo svesti na minimalno povezujuće stablo.
Dodajmo jedan novi, virtuelni čvor koji predstavlja izvor signala. Za svako selo \(i\) dodajemo granu između virtuelnog čvora i sela \(i\) sa težinom \(a_i\). Biranje te grane znači da u selu \(i\) gradimo repetitor. Sve postojeće kablove ostavljamo kao grane između sela sa njihovim cenama.
Sada treba povezati sva sela i virtuelni čvor minimalnom ukupnom cenom. To je upravo problem minimalnog povezujućeg stabla. Ako rešenje izabere granu od virtuelnog čvora do nekog sela, u tom selu gradimo repetitor. Ako izabere granu između dva sela, između njih postavljamo kabl.
Za pronalaženje minimalnog povezujućeg stabla koristimo postupak sa sortiranjem grana. Sve grane sortiramo po ceni rastuće i dodajemo ih redom ako spajaju dve različite komponente. Komponente pratimo union-find strukturom.
Pošto postoji grana od virtuelnog čvora do svakog sela, graf je uvek povezan, pa rešenje uvek postoji.
Složenost postupka je \(O((n + m) \log(n + m))\) zbog sortiranja grana.
#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:
vector<Grana> grane;
void sortiraj_grane()
{
sort(grane.begin(), grane.end(), [](const Grana &g1, const Grana &g2) {
return g1.cena < g2.cena;
});
}
public:
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;
for (const Grana &grana : grane) {
int grupa_u = UF_nadji_grupu(grana.u);
int grupa_v = UF_nadji_grupu(grana.v);
// Ako su krajevi vec povezani, ova grana bi napravila ciklus.
if (grupa_u == grupa_v) {
continue;
}
UF_unija(grana.u, grana.v);
ukupna_cena += grana.cena;
}
return ukupna_cena;
}
};
int main()
{
int n, m;
cin >> n >> m;
Graph *G = new Graph();
int virtuelni_cvor = n;
UF_inicijalizacija(n + 1);
for (int i = 0; i < n; i++) {
int cena_repetitora;
cin >> cena_repetitora;
G->dodaj_granu(virtuelni_cvor, i, cena_repetitora);
}
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;
}