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.

TODO