navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:zkouska2014_5 [2014/01/30 20:58] sioca vytvořeno |
courses:a4m33pal:zkouska2014_5 [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 12: | Řádek 12: | ||
| ===== Řešení ===== | ===== Řešení ===== | ||
| - | TODO | + | 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í): {{:courses:a4m33pal:src.zip|}} | ||
