Ak vyštartujeme z ľubovoľného prameňa p1 a sledujúc smerovníky prechádzame postupne pramene p2, p3,..., po najviac N krokoch sa nám stane, že prídeme k prameňu pk+1, pri ktorom sme už boli, t.j. pk+1=pj pre nejaké j<=k. Keďže smerovník ukazujúci na prameň j bol vyrobený iba jeden, musí byť buď pk=pj-1, alebo j=1. Ak je k najmenšie také, že pk+1=pj, j<=k, potom j=1 a teda pramene p1,...,pk tvoria cyklus. Takýmto spôsobom vieme pre každý prameň určiť cyklus, do ktorého patrí.
Vzorový program využíva fakt, že ak vymeníme smerovníky pri dvoch prameňoch, ktoré patria do rovnakého cyklu, tento cyklus sa nám rozdelí na dva, t.j. počet cyklov sa zvýši o 1. Ak naopak vymeníme smerovníky pri prameňoch z rôznych cyklov, tieto dva cykly sa spoja do jedného.
Označíme si pramene, ktoré patria do toho istého cyklu ako prameň 1. Postupne budeme hľadať ďalšie cykly, ktoré budeme pripájať k cyklu obsahujúcemu prameň 1. Vždy, keď nájdeme nový cyklus, označíme si všetky pramene, ktoré doňho patria a zároveň spravíme výmenu smerovníkov, ktorou sa tento cyklus pripojí k cyklu obsahujúcemu prvý prameň. Všimnime si, že novovzniknutý cyklus obsahuje práve doposiaľ označené pramene. Ďalší cyklus potom hľadáme medzi neoznačenými prameňmi.
Na záver vymeníme jeden smerovník z každého cyklu so smerovníkom pri niektorom prameni z cyklu obsahujúceho prameň 1, t.j. postupne vymieňame smerovník pri prameni 1 so smerovníkmi pri prameňoch označených -1 (reprezentanti cyklov). Potrebný počet výmen je o jednotku menší ako počet cyklov.
Takto zredukovanú úlohu budeme riešiť metódou dynamického programovania. Označme Ei,j (1<=q i<=q N, 0<=q j<=q K) dĺžku najkratšej trasy končiacej v deň j v meste i, takej, že sme videli filmy p1, p2,..., pj a pritom sme posledný film pj videli v meste i. Ak hodnota Ei,j neexistuje (t.j. neexistuje trasa popísaných vlastností), položíme Ei,j rovno nekonečnu.
Hodnoty Ei,j budeme postupne počítať z iných skôr vypočítaných hodnôt Ei,j a z hodnôt hi,j. Začneme zrejme takto: E1,0 = 0 a Ei,0 je nekonečno (2<=i<=N).
Počítajme hodnotu Ei,j pre 1<=j<=N. Máme dve možnosti: V meste i nehrajú film pj. Trasa požadovaných vlastností končiaca v meste i neexistuje, preto Ei,j je nekonečno.
Druhá možnosť je, že film pj v meste i hrajú. Rozoberme túto možnosť.
Na to, aby sme videli filmy p1,p2,..., pj sme museli vidieť filmy
p1,p2,..., pj-1. Film pj-1 sme mohli vidieť v nejakom meste
s. Do mesta s sme sa pritom zrejme dostali najkratšou trasou, končiacou v
tomto meste. Dĺžka tejto trasy je Es,j-1.
Z mesta s do mesta i sme takisto museli ísť najkratšou cestou.
Teda dĺžka takejto trasy bude Es,j-1 + hs,i. Prostým
vyskúšaním všetkých možných miest s dostaneme dĺžku najkrašej cesty
Ei,j.
Ei,j = min { Es,j-1 + hs,i | 1<=q s<=q N }
Najkratšia trasa, potrebná na zhliadnute všetkých K filmov končí v nejakom
meste i. Stačí nám teda vybrať z dĺžok trás, ktoré končia
v jednotlivých mestách tú najmenšiu. Pre dĺžku optimálnej trasy E teda platí
E := min { Ei,K | 1<=q i<=q N }
Ostáva nám ešte zistiť, cez ktoré mestá vlastne optimálna trasa vedie.
Označme Di,j mesto, z ktorého sme prišli v deň j
do mesta i, ak
by sme išli po optimálnej trase končiacej v meste i v deň j.
Hodnotu Di,j budeme počítať súbežne s hodnotou Ei,j. Di,j
bude vlastne to mesto s, pre ktoré bude Es,j-1 + hs,i minimálne.
Mesto, v ktorom končí hľadaná optimálna trasa (t.j. také, pre ktoré je Ei,K minimálne) označme xK. Potom predchádzajúce mesto na optimálnej trase bude xK-1 = DxK,K. Vo všeobecnosti mesto na optimálnej trase, z ktorého sme prišli do mesta xi bude mesto xi-1 = Dxi,i.
Nakoniec venujme pár slov otázke, ako vzdialenosti hi,j ( 1<=qi,j<=qN) medzi jednotlivými mestami počítať. Použijeme štandardný Floyd-Warshallov algoritmus. Vstupom tohto algoritmu je matica hi,j (1<=i,j<=N), obsahujúca dĺžky ciest, spájajúcich jednotlivé dvojice miest (pre cestu vedúcu medzi mestami i a j s dĺžkou l položíme hi,j=hj,i=l, ak medzi i a j nevedie žiadna cesta, položíme hi,j=hj,i je nekonečno). Výstupom algoritmu je matica h, v ktorej hi,j je minimálna vzdialenosť, ktorú musíme precestovať, aby sme sa dostali z mesta i do mesta j.
Algoritmus bude pracovať v N cykloch. Po vykonaní k-teho cyklu (0<= k<=N) bude platiť, že hi,j je dĺžka najkratšej trasy z mesta i do mesta j, ktorá prechádza len cez mestá s číslom menším alebo rovným k. Na začiatku (t.j. po vykonaní 0 cyklov) je v hi,j uložená dĺžka priamej trasy bez prechádzania cez iné vrcholy. Pri vykonávaní k-teho cyklu, dĺžka trasy hi,j môže byť buď rovnaká ako v predchádzajúcom cykle (ak nevyužijeme možnosť viesť trasu z mesta i do mesta j cez mesto k), alebo rovná hi,k+hk,j (ak trasu z i do j vedieme cez mesto k). Vždy si samozrejme vyberieme kratšiu možnosť.
h
, v ktorom aj počítame
vzdialenosti medzi mestami F-W algoritmom. Na výpočet si nepotrebujeme pamätať
všetky hodnoty Ei,j, stačí si pamätať iba dva stĺpce pre j a j+1.
To robíme v poli optim
, pričom optim[0]
obsahuje
hodnoty Ei,j pre j párne a optim[1]
pre j nepárne.
Ak však chceme zrekonštruovať optimálnu trasu, potrebujeme si pamätať aspoň
hodnoty Di,j. Na tie nám však stačí typ byte
. Hodnoty
Di,j máme v poli pred
, ktoré je vo vzorovom programe
alokované dynamicky, aj keď obmedzenia v zadaní dovoľovali použiť statické
pole.