courses:a4m33pal:uloha1-2015 [OI-Wiki]

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.

===== Jak na to =====

== Můj postup 10/10 (C/C++) ==
Ze zadání vyplývá, že úloha má co dočinění s kostrou, v tomto případě minimální (Minimum spanning tree).

Myšlenka řešení je následující:
Na budování kostry bude využit Kruskalův algoritmus, s podporou union find operací. Dle zadání budeme potřebovat dvě pole, nodes[N], edges[M]. Pole nodes slouží pro union find, pole edges obsahuje seznam hran. Nejdříve je nutné setřídit pole edges dle ceny hrany vzestupně. Pole nodes se inicializuje tak, aby každý prvek měl za svého předka sama sebe. Nyní se bude procházet pole edges a provádět operace union na jednotlivé uzly. Zde je důležité si uvědomit, že kostra může mýt maximálně N - 1 hran, tedy po dosažení tohoto počtu lze iteraci ukončit, union nic nového nespojí.

Pseudokód pro Union Find lze nalézt na wiki [[https://en.wikipedia.org/wiki/Disjoint-set_data_structure]]. Je nutné upravit union, tak, aby vyhověl zadání. Jedna z možných modifikací je následující:

  * ze zadání víme, které uzly spojuje nejlevnější hrana (dále označeny root_x a root_y). Virtuálně tuto hranu odstraníme. Tyto uzly budou tvořit vrcholy stromů při operaci union a nebudeme je spojovat.
  * pokud operace FIND pro zkoumanou hranu zjistí, že byly vráceny kořeny root_x a root_y, tato hrana se nepoužije, neboť jejím zavedením bychom vytvořili cyklus skrze virtuální hranu mezi root_x a root_y.
  * pokud jeden z výsledků FIND(x) nebo FIND(y) je roven root_x nebo root_y, bez okolků připojíme x pod (root_x | root_y)


V poli nodes by nyní měly být vytvořeny 2 stromy s vrcholy root_x a root_y. Jelikož je pole edges setříděné, stačí operace FIND(x) ukončit po detekci hrany hrana.cena > high. V této fázi by se neměl využívat optimalizovaný find, ale pouze FIND_READ_ONLY(x), tj. který nemodifikuje pole nodes. Jelikož bude potřeba výsledky setřídit dle pravidel výstupu, lze vytvořit pomocné pole, které se posléze zatřídí, ale lepší varianta je použít pole edges a začít přepisovat od začátku se zjištěnými kandidáty, jelikož již není potřeba pole edges udržovat pro potřeby Kruskala.



~~DISCUSSION~~

courses/a4m33pal/uloha1-2015.txt · Poslední úprava: 2025/01/03 18:28 (upraveno mimo DokuWiki)

Nahoru