Pera je zadužen za postavljanje ozvučenja na koncertu jednog benda. Potrebno je da poveže zvučnike kablovima tako da svaka dva zvučnika budu povezana kablovima (potencijalno na tom putu može imati još zvučnika), ali ne sme na taj način formirati ciklus. Poznato je da li između data dva zvučnika može fizički provući kabl i koja bi bila cena tog kabla. Kako bend ima dosta novca, spremni su da isplate bilo koju sumu za troškove kablova, makar ona bila i maksimalna. Znajući to, Pera hoće da izračuna koliko bi novca zaradio ako bi kablove postavio tako da im ukupna cena bude minimalna. Izračunati tu vrednost.
Sa standardnog ulaza se učitava broj zvučnika \(N\) i broj potencijalnih kablova \(M\) (\(1 \leq n, m \leq 10^5\)), a zatim u sledećih \(M\) redova brojevi \(x\), \(y\) i \(c\), gde svaki red označava da se između zvučnika \(x\) i \(y\) može postaviti kabl sa cenom \(c\).
Ispisati na standardni izlaz razliku maksimalne i minimalne cene kablova takvih da ispunjavaju zahteve benda.
5 8 0 1 4 0 2 7 0 4 2 1 2 6 1 3 4 1 4 3 2 4 1 3 4 9
16
Potrebno je izabrati kablove tako da svi zvučnici budu povezani, ali da se ne formira ciklus. Takav skup kablova predstavlja povezujuće stablo grafa.
Pošto se traži razlika maksimalne i minimalne moguće cene takvog skupa kablova, dovoljno je odrediti cenu minimalnog povezujućeg stabla i cenu maksimalnog povezujućeg stabla. Njihova razlika je traženi odgovor.
Minimalno povezujuće stablo određujemo Primovim algoritmom. Krećemo od nekog čvora, a zatim u svakom koraku biramo najjeftiniju granu koja povezuje već izabrani deo stabla sa nekim još neizabranim čvorom. Na taj način ne pravimo ciklus, a uvek dodajemo najjeftiniju moguću granu koja širi trenutno stablo.
Maksimalno povezujuće stablo računamo na isti način, samo umesto najjeftinije biramo najskuplju moguću granu. Zato koristimo red sa prioritetom koji na vrhu čuva najveću cenu.
Ako graf ima više komponenti povezanosti, postupak se pokreće za svaku komponentu posebno. Početni čvor svake komponente ima cenu \(0\), jer se za njega ne bira ulazna grana.
Složenost oba postupka je \(O(m \log n)\), pa je i ukupna složenost rešenja \(O(m \log n)\).
#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 min_cena() {
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 max_cena() {
priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
vector<int> kljuc(broj_cvorova, -1);
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, v, w);
}
cout << G->max_cena() - G->min_cena() << endl;
delete G;
return 0;
}