7. Ohavný čin vzorové riešenie

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

16

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);
}