Augmentations of spanning tree

(Pokud někdo můžete, doplňte sem prosím originální zadání)

Dostanete graf, popsaný počtem uzlů N, počtem hran M, počtem augmentací D a poté seznamem hran s jejich koncovými uzly a váhami. Vaším úkolem je vyrobit minimální kostru grafu a poté spočítat váhu její D-té augmentace. Výsledkem je jediné číslo značící váhu této augmentace.

Jedna augmentace vznikne tak, že ze všech hran grafu, které nejsou obsaženy v aktuální kostře vyberu jednu (e1), co možná nejdražší a vložím jí do kostry. Poté z „kostry“ (která nyní nutně obsahuje cylkus) odeberu jinou hranu (e2), co možná nejlevnější tak, aby mi opět vznikla kostra. Výsledná kostra musí mít vyšší váhu, než kostra původní a tato váha musí být nejvyšší možná ze všech možných aktuálních kombinací e1,e2. Pokud jsou možné více, než jedna dvojice e1,e2 dávající nejvyšší váhu, beru tu dvojici, která má vyšší váhu hrany e2.

Nejprve si vytvořím minimální kostru (kruskal, jarník …). Zvolil jsem Kruskala, protože množina seřazených hran se mi později hodí. Celou dobu si držím dvě množiny hran: hrany v kostře a hrany mimo kostru. Obě seřazené.

Pro každou augmentaci: * vyberu nejdražší hranu mimo kostru * označím jí k přidání do kostry * spustím BFS z obou jejích koncových uzlů a ukládám si předchůdce každého uzlu * jakmile narazím na uzel, ve kterém už jsem byl, našel jsem vytvořený cyklus * procházím z nalezeného uzlu zpět k uzlům přidané hrany a aktualizuju si nejlevnější hranu cylku * nejlevnější hranu označím k odebrání z kostry * počítám váhu takto vzniklé kostry a označím jako možné následující maximum * spustím tento cylkus znovu pro druhou největší hranu mimo graf …

Cyklus končí, jakmile by váha možné přidané hrany už nemohla v součtu s aktuální váhou kostry-1 (musím nějakou hranu odebrat tak budu předpokládat, že tu nejlevnější) převýšit nebo alespoň vyrovnat momentálně uložené následující maximum.

Po skončení cylku přidám označenou drahou a odeberu označenou levnou hranu. Updatuju momentální váhu kostry.

Opakujte až do D-té augmentace (minimální kostra se počítá jako první augmentace)

Zdroják a data (12/12 - o kousek rychlejší než referenční): src.zip