Zadanie
Kleofáš sa vlúpal do základne KSP, aby z organizátorských serverov ukradol zadania ďalšej série (ktoré už sú samozrejme dávno pripravené). Ale spustil sa alarm a do T2 už mieria vytočení rooti, takže Kleofáš si musí pohnúť a všetky príklady ukradnúť čo najrýchlejšie.
Úloha
Na serveri je \(n\) príkladov. Kleofáš chce všetky stiahnuť na svoj notebook. Stiahnuť príklad číslo \(i\) trvá \(d_{i,i}\) sekúnd. Ale ak sa podobá na nejaký už stiahnutý príklad \(j\), netreba ho sťahovať celý – stačí za \(d_{i,j}\) sekúnd stiahnuť rozdiely medzi nimi.
Príklady je možné sťahovať v ľubovoľnom poradí. Zistite, za koľko sekúnd dokáže Kleofáš stiahnuť všetky príklady.
Formát vstupu
V prvom riadku vstupu je číslo \(n\) (\(1\leq n \leq 1\,000\)) udávajúce počet príkladov. Nasleduje \(n\) riadkov s \(n\) číslami, z čoho \(j\)-te číslo \(i\)-teho riadku je hodnota \(d_{i,j}\) (\(1\leq d_{i,j} \leq 10^9\)). Pre \(i=j\) je to čas prenosu celého príkladu, zatiaľčo pre \(i\neq j\) je to čas prenosu rozdielov medzi príkladmi \(i\) a \(j\). Platí, že pre každé \(i,j\) je \(d_{i,j}=d_{j,i}\).
Formát výstupu
Vypíšte, koľko sekúnd treba na stiahnutie všetkých príkladov.
Príklad
Input:
5
4 7 7 6 7
7 11 4 3 4
7 4 8 7 6
6 3 7 1 5
7 4 6 5 5
Output:
16
Najprv stiahneme celý štvrtý príklad, potom jeho rozdiely od druhého, a keď už máme druhý, stiahneme jeho rozdiely od tretieho a piateho príkladu. Prvý príklad tiež stiahneme celý, lebo sa veľmi nepodobá na žiaden iný.
Chceme stiahnuť \(n\) súborov, pričom každý súbor môžeme buď stiahnuť celý, alebo si ušetriť čas a stiahnuť iba jeho rozdiely oproti nejakému inému súboru, ktorý už máme stiahnutý. O všetkom z toho vieme, koľko by to trvalo.
Základná myšlienka riešenia je previesť naše zadanie na problém najlacnejšej kostry. To je štandardná úloha, v ktorej dostaneme neorientovaný ohodnotený graf, a máme vybrať takú podmnožinu hrán, že má minimálnu cenu a graf obsahujúci len tieto hrany bude súvislý. Takže keď v grafe nájdeme najlacnejšiu kostru, stále sa po nej zvládneme dostať odvšadiaľ všade, ale celkový súčet váh hrán bude minimálny.
Tak to skúsme. Povedzme, že každý vrchol bude reprezentovať jeden stiahnutý súbor, a medzi každými dvoma vrcholmi bude hrana s takou váhou, koľko trvá stiahnuť rozdiely medzi tými súbormi. Keby sme v tomto grafe našli najlacnejšiu kostru, zistili by sme, ako by sa dalo stiahnuť všetky súbory, keď už jeden máme.
Ale zatiaľ sme obmedzení len na sťahovanie rozdielov. Stále sme sa nedozvedeli, ktoré súbory máme stiahnuť celé. Našťastie už nechýba veľa: Stačí do grafu pridať nový vrchol, ktorý predstavuje situáciu “zatiaľ žiadne súbory nemám”. Medzi každým súborom a týmto novým vrcholom bude hrana s takou váhou, koľko trvá stiahnuť celý ten súbor.
Veľkosť najlacnejšej kostry pre tento graf je naša odpoveď. Najlacnejšia kostra vlastne hovorí návod, ako všetko najrýchlejšie stiahnuť. Súbory, čo susedia s vrcholom “ešte nič nemám”, stiahneme celé, a potom podľa kostrových hrán postupne stiahneme všetko ostatné (tam už stačí sťahovať rozdiely).
Hľadanie najlacnejšej kostry
Na naše konkrétne zadanie už môžme zabudnúť. Pozrime sa, ako sa hľadá najlacnejšia kostra vo všeobecnom grafe s \(v\) vrcholmi a \(e\) hranami. Jeden z algoritmov, čo túto úlohu vedia riešiť, sa volá Primov algoritmus.
Primov algoritmus buduje výslednú kostru vrchol po vrchole. Na začiatku bude kostra mať jediný vrchol (je jedno, ktorý). Potom v každom ťahu našu kostru o niečo zväčšíme – nájdeme najlacnejšiu hranu, ktorá prepája nejaký kostrový a nejaký nekostrový vrchol, a pridáme ju do našej kostry. To opakujeme, až kým nie je v kostre každý vrchol (čiže \(v-1\) ráz). Kostra, ktorú týmto postupom nájdeme, je zaručene najlacnejšia.
Ako nájdeme tú najlacnejšiu hranu? Väčšinou sa na to používa binárna halda, ale teraz si ukážeme, ako to spraviť lineárnym prehľadávaním. Budeme mať pole, v ktorom si pre každý vrchol \(p\) uložíme cenu pridania \(p\) do kostry – čiže najlacnejšiu hranu z ľubovoľného kostrového vrchola do \(p\). Keď vyberáme, ktorý vrchol pridať, proste zaradom prejdeme celé toto pole a vyberieme najlacnejší. Z tohto vrchola sa tým pádom stáva kostrový vrchol, takže sa pozrieme na všetkých jeho nekostrových susedov a zapíšeme do poľa, či sme pre nich nenašli lepšiu cenu. A to je celé.
Tento algoritmus má časovú zložitosť \(O(v^2)\). To je zvyčajne dosť veľa – keby sme použili Primov algoritmus s binárnou haldou, mali by sme zložitosť iba \(O(e \log v)\), a Kruskalov algoritmus by nám tiež dal \(O(e \log v)\). Lenže my máme kompletný graf, kde \(v=O(n)\) a \(e=O(n^2)\). V ňom majú Kruskal aj haldový Prim časovú zložitosť \(O(n^2 \log n)\), zatiaľ čo trápnemu lineárnemu prehľadávaniu stačí \(O(n^2)\). V praxi to síce nie je veľký rozdiel, takže asi budú fungovať aj programy s pomalšími algoritmami, ale v popise ste za to mohli stratiť jeden bod.
#include <cstdio>
#include <vector>
using namespace std;
#define For(i,n) for(int i=0; i<(n); i++)
int main() {
int n;
int G[1047][1047];
scanf("%d",&n);
For(i,n) For(j,n) scanf(" %d",&G[i][j]);
long long res=0;
vector<int> V; V.resize(n,1000000047);
For(i,n) V[i]=G[i][i];
For(i,n) {
int p=-1;
For(j,n) if(V[j]!=-1 && (p==-1 || V[p]>V[j])) p=j;
res+=V[p];
V[p]=-1;
For(j,n) if(V[j]>G[p][j]) V[j]=G[p][j];
}
printf("%lld\n",res);
}
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.