navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:zkouska2014_3 [2014/01/16 16:14] trnkami1 vytvořeno |
courses:a4m33pal:zkouska2014_3 [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== Název předmětu ====== | + | ====== Shortcut edges ====== |
| + | We say that an edge (x,y) in a directed simple graph G is a shortcut edge when there is a path in G from x to y which length is at least 2. Let the cost of a shortcut edge(x,y) be the length of the longest path from x to y in G. | ||
| + | ===== The task ===== | ||
| + | Given a directed acyclic graph G determine the sum of costs of all its shortcut edges. | ||
| - | * Stránky předmětu: | ||
| - | * Přednášející: | ||
| - | * Cvičící: | ||
| - | ===== Cvičení ===== | + | ====== Postup ====== |
| - | + | Řešení pomocí Floyd-Warshalla je neučinné. Projde na 2/12. | |
| - | + | ||
| - | + | ||
| - | ===== Zkouška ===== | + | |
| - | + | ||
| - | + | ||
| - | ~~DISCUSSION~~ | + | |
| + | Postup na 11/12: | ||
| + | Prochazel jsem graf pro kazdej vrchol pomoci DFS. S tim, ze jsem od spoda propagoval cenu vrcholu - ty nejnizsi byli koncovy a urcite nemeli zadne sousedy, ty nad tim meli za sousedy maximalne ty bez zadneho, atd. Uz projity vrcholy jsem uzaviral a pouzival uz spocitanou cenu. Na konec se pro vsechny sousedy zkontroluje jejich nejvetsi vzdelanost a to jsou zkratky. | ||
| + | Odkaz na zdrojaky: | ||
| + | {{:courses:a4m33pal:pal.zip|}} | ||
