1. Takto sa obsadzuje graf vzorové riešenie

3 2
10 5
20 10
10 3
1 2 22
2 3 200

140

5 4
5 1
5 1
5 100
5 100
10 100
1 3 5
2 4 5
3 4 10
4 5 10

10

Ako vždy, začnime sériou pozorovaní. Uvedomme si, že naším cieľom je iba dobyť všetky vrcholy a teda nemusíme dobyť všetky hrany. Dokonca hrany, ktoré dobyjeme ani nemusia vytvárať kostru nášho grafu. Ak si preto zoberieme nejaké optimálne výsledné riešenie, tak dobyté hrany budú vytvárať niekoľko samostatných komponentov. Vieme teraz vypočítať koľko nás takéto dobytie stálo?

Samozrejme, komponenty sa nijak neovplyvňujú, keďže figúrky medzi nimi nemôžu prechádzať. Každý teda musíme započítať zvlášť. Takisto je jasné, že v jednom komponente chceme figúrky pridávať iba do jedného vrcholu. Toho, v ktorom je to najlacnejšie. Cenu pridania jednej figúrky do vrcholu \(v\) nám určuje hodnota \(b_v\). Preto chceme nájsť v danom komponente vrchol s najmenšou hodnotou \(b_v\). Označme si túto hodnotu premennou \(cena\).

A koľko figúrok potrebujeme na to, aby sme dobyli celý tento komponent? Určite potrebujeme dobyť každý vrchol. Na dobytie vrchola \(v\) potrebujeme \(a_v\) figúrok. Zo všetkých vrcholov v tomto komponente preto nájdeme ten, na ktorého dobytie treba najviac figúrok, teda má najväčšiu hodnotu \(a_v\), a túto hodnotu si označíme premennou \(pocet_v\). Je jasné, že na dobytie všetkých vrcholov potrebujeme aspoň \(pocet_v\) figúrok.

Ani takýto počet však nemusí postačovať, mohli sme sa totiž rozhodnúť v tomto komponente dobyť hranu \(e\), na ktorej dobytie potrebujeme \(c_e\) figúrok, pričom \(c_e > pocet_v\). V tomto komponente sa teda musíme pozrieť aj na všetky dobyté hrany a nájsť tú, ktorá má najväčšiu hodnotu \(c_e\). Túto hodnotu si označíme ako \(pocet_e\). Všimnite si, že v tomto komponente môžu byť aj drahšie hrany, ktoré sme sa však rozhodli nedobyť a preto nás nemusia zaujímať.

Teraz si rozmyslite, že ak naozaj vytvoríme \(\max(pocet_v, pocet_e)\) figúrok vo vrchole, v ktorom to stojí \(cena\) peňazí, podarí sa nám potom dobyť celý tento komponent, zaplatíme za to \(cena \cdot \max(pocet_v, pocet_e)\) peňazí a táto hodnota je najmenšia možná.

Ďalšie dobré pozorovanie je, že sa nám nikdy neoplatí dobýjať hranu z oboch strán – teda tak, že na oboch jej koncoch je nenulový počet figúrok. Ak by sme totiž na jednom konci mali \(x\) figúrok a na druhom \(y\), tak sa radšej pozrieme, do ktorých vrcholov sme pôvodne pridali tieto figúrky, vyberieme si ten lacnejší a pridáme doňho \(x+y\) figúrok. Uvedomme si, že stále budeme vedieť dobyť tú istú časť grafu a určite to nebude drahšie.

No a nakoniec, povedzme si, že chceme dobyť nejakú hranu \(e\), na ktorej dobytie treba \(c_e\) figúrok. Ak si v grafe zoberieme iba hrany, ktorých dobytie je nanajvýš také drahé, tak sa nám opäť vytvorí viacero súvislých komponentov. Ak však máme dostatok figúrok na dobytie hrany \(e\), určite budeme mať dosť figúrok na dobytie každej hrany, ktorá bola nanajvýš taká drahá a je v rovnakom komponente ako hrana \(e\). Ak nás to teda nebude stáť nič naviac, tak sa nám tieto hrany určite oplatí dobyť. Vďaka nim sa totiž vieme dostať k viacerím vrcholom, čo nám dáva šancu nájsť vrchol s nízkou hodnotou \(b_v\), v ktorom tých \(c_e\) figúrok ktoré potrebujeme, vieme vyrobiť.

Myšlienka a implementácia

Nepripomína vám to niečo? Komponenty, hrany lacnejšie ako nejaká hrana \(e\)? Lebo mne to smrdí Kruskalom – algoritmom na hľadanie najlecnejšej kostry. Aj ohľadom zložitosti tento algoritmus sedí, takže to vyzerá, že sme na dobrej ceste.

Kruskalov algoritmus začína tým, že si usporiada hrany od najlacnejšej po najdrahšiu a potom ich postupne pridáva do grafu. Pritom si, najčastejšie pomocou union-findu, udržiava množinu súvislých komponentov. Pri pridávaní hrany najskôr skontroluje, či daná hrana nevedie medzi dvoma vrcholmi, ktoré už patria tomu istému komponentu. Ak áno, takúto hranu ignoruje. V opačnom prípade ju však do grafu vloží a spojí komponenty, do ktorých patrili koncové vrcholy tejto hrany.

Ako tento algoritmus upravíme tak, aby riešil náš problém? Zjavne najdôležitejšia je operácia pridávania hrany. Už teda existujú nejaké súvislé komponenty a predpokladajme, že o každom z nich vieme, ako čo najlacnejšie dobyť všetky vrcholy v ňom. Čo sa zmení pridaním hrany \(e\)?

Hrana \(e\) môže spájať vrcholy, ktoré patria do toho istého komponentu. Tak ako v klasickom Kruskalovi však túto hranu môžeme ignorovať. Ak už vieme ako najlacnejšie dobyť všetky vrcholy v danom komponente, pridanie hrany, na ktorej dobytie potrebujeme viac figúrok ako na zvyšné hrany v tomto komponente, nám určite riešenie nezlepší.

Takže sa zamerajme na prípad, keď hrana \(e\) vedie medzi dvoma komponentami. Ak sa rozhodneme túto hranu dobyť, bude platiť naše posledné pozorovanie. Teda následne budeme vedieť zadarmo dobyť aj zvyšné hrany v týchto dvoch komponentoch, čím nám vznikne jeden súvislý komponent. A koľko stojí dobytie tohto spoločného komponentu? Podľa prvého pozorovania musíme nájsť hodnoty \(cena\), \(pocet_v\) a \(pocet_e\). Zjavne \(pocet_e = c_e\), keďže aktuálne pridávaná hrana je drahšia ako všetky doteraz pridané hrany. Ostáva teda nájsť vrchol, na ktorého dobytie potrebujeme najviac figúrok a vrchol, v ktorom je pridávanie figúrok najlacnejšie.

Aby sme tieto dve hodnoty vedeli vypočítať rýchlo, budeme si pre každý komponent naviac pamätať aj jeho hodnotu \(cena\) a \(pocet_v\). Pri spojení dvoch komponentov potom stačí zobrať minimum z ich hodnôt \(cena\) a maximum z ich hodnôt \(pocet_v\). Vďaka tomu dokážeme v konštantnom čase vypočítať, koľko nás stojí dobytie tohto komponentu.

Občas sa nám však hranu \(e\) nemusí oplatiť dobyť. Napríklad preto, lebo má príliš veľkú hodnotu \(c_e\). Môžeme sa však tváriť, že sa tieto dva komponenty spojili aj tak. Stále vieme vypočítať, za koľko najmenej dobyť všetky vrcholy tohto komponentu. Jednoducho si zoberieme súčet dobytí jednotlivých komponentov. A do budúcna nám to nič nepokazí, lebo ak sa niekedy v budúcnosti rozhodneme dobyť hranu, ktorá bude zasahovať do tohto komponentu tak budeme vedieť zadarmo dobyť aj hranu \(e\) (lebo je lacnejšia) a teda sa tváriť, že vlastne celý čas boli spolu. (Toto je asi najpodstatnejšia a teda aj najťažšia časť myšlienky tohto riešenie. Odporúčam prečítať ešte raz a poriadne požuť.)

Samotný algoritmus je potom naozaj len veľmi jemnou obmenou Kruskalovho algoritmu. Pre každý komponent si budeme pamätať tri hodnoty – \(cena\) (ako najlacnejšie viem vyrábať figúrky), \(pocet_v\) (koľko najviac figúrok potrebujem na dobytie nejakého vrcholu v tomto komponente) a \(riesenie\) (najlacnejšia cena dobytia všetkých vrcholov tohto komponentu). Na začiatku tvorí každý vrchol samostatný komponent a spomenuté tri hodnoty sú nastavené na \(b_v\), \(a_v\) a \(b_v \cdot a_v\).

Následne budeme spracovávať hrany od tej s najmenším \(c_e\) po tú s najväčším. Pre každú hranu sa pozrieme, či spája vrcholy z rôznych komponentov. Ak nie, tak túto hranu ignorujeme. Inak si vypočítame, za akú cenu vieme dobyť všetky vrcholy v tomto komponente ak dobyjeme hranu \(e\) (\(\min(cena, cena') \cdot \max(c_e, pocet_v, pocet_v')\)) alebo ak ju nedobyjeme (\(riesenie + riesenie'\)). Vyberieme si tú lacnejšiu možnosť, komponenty spojíme dokopy a príslušne upravíme hodnoty \(cena\), \(pocet_v\) a \(riesenie\) pre tento spojený komponent.

Na konci nám ostane jeden komponent a jeho hodnota \(riesenie\) nám hovorí, ako najlacnejšie dobyť všetky vrcholy v celom grafe.