navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:zkouska2015_1 [2015/01/06 15:56] jirkamat |
courses:a4m33pal:zkouska2015_1 [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 3: | Řádek 3: | ||
| {{:courses:a4m33pal:pal2015-1-1.png?nolink&500|}} | {{:courses:a4m33pal:pal2015-1-1.png?nolink&500|}} | ||
| ===== Zadání ===== | ===== Zadání ===== | ||
| - | === Otočení hrany === | + | ==== Otočení hrany ==== |
| Příklad acyklického grafu s osmi vrcholy označenými 0, 1, ..., 7, kde váhy jsou připsány u jednotlivých vrcholů. Po změně orientace hrany (7, 1) vznikne silně souvislá komponenta obsahující vrcholy 0, 1, 3, 4, 7 s celkovým součtem vah 27. | Příklad acyklického grafu s osmi vrcholy označenými 0, 1, ..., 7, kde váhy jsou připsány u jednotlivých vrcholů. Po změně orientace hrany (7, 1) vznikne silně souvislá komponenta obsahující vrcholy 0, 1, 3, 4, 7 s celkovým součtem vah 27. | ||
| - | Úloha | + | === Úloha === |
| Je dán acyklický prostý graf G, jehož každý vrchol má kladnou celočíselnou váhu. Mame v G změnit orientaci právě jedné hrany tak, aby v G vznikla silně souvislá komponenta s maximálním možným součtem vah jejích vrcholů. | Je dán acyklický prostý graf G, jehož každý vrchol má kladnou celočíselnou váhu. Mame v G změnit orientaci právě jedné hrany tak, aby v G vznikla silně souvislá komponenta s maximálním možným součtem vah jejích vrcholů. | ||
| - | Vstup | + | == Vstup == |
| První řádek obsahuje dvě celá kladná čísla N, M oddělená mezerou představující po řadě počet vrcholů a hran v grafu. Vrcholy jsou očíslovány od 0 do N−1. Za prvním řádkem následuje N řádků, na každém je uvedena váha jednoho vrcholu v rostoucím pořadí čísel vrcholů. Dále následuje M řádků, každý specifikuje jednu hranu, na řádku jsou uvedena dvě čísla oddělená mezerou představující po řadě číslo vstupního a výstupního vrcholu hrany. Hrany jsou uvedeny v libovolném pořadí. | První řádek obsahuje dvě celá kladná čísla N, M oddělená mezerou představující po řadě počet vrcholů a hran v grafu. Vrcholy jsou očíslovány od 0 do N−1. Za prvním řádkem následuje N řádků, na každém je uvedena váha jednoho vrcholu v rostoucím pořadí čísel vrcholů. Dále následuje M řádků, každý specifikuje jednu hranu, na řádku jsou uvedena dvě čísla oddělená mezerou představující po řadě číslo vstupního a výstupního vrcholu hrany. Hrany jsou uvedeny v libovolném pořadí. | ||
| Hodnota N nepřesáhne 5000, hodnota N × M nepřesáhne 2.5×108. | Hodnota N nepřesáhne 5000, hodnota N × M nepřesáhne 2.5×108. | ||
| - | Výstup | + | == Výstup == |
| Výstup obsahuje jeden řádek s třemi celými čísly oddělenými mezerou. První dvě určují počáteční a koncový vrchol hledané hrany před změnou její orientace, třetí představuje součet vah vrcholů ve vzniklé silně souvislé komponentě. Pokud podmínky úlohy splňuje více hran, objeví se na výstupu pouze ta, která má lexikograficky nejmenší zápis (číslo počátečního vrcholu a číslo koncového vrcholu). | Výstup obsahuje jeden řádek s třemi celými čísly oddělenými mezerou. První dvě určují počáteční a koncový vrchol hledané hrany před změnou její orientace, třetí představuje součet vah vrcholů ve vzniklé silně souvislé komponentě. Pokud podmínky úlohy splňuje více hran, objeví se na výstupu pouze ta, která má lexikograficky nejmenší zápis (číslo počátečního vrcholu a číslo koncového vrcholu). | ||
| Je zaručeno, že hledaná silně souvislá komponenta obsahuje alespoň tři vrcholy, hodnota výsledného součtu nepřekročí 109. | Je zaručeno, že hledaná silně souvislá komponenta obsahuje alespoň tři vrcholy, hodnota výsledného součtu nepřekročí 109. | ||
| - | Příklad 1 | + | == Příklad 1 == |
| **Vstup** \\ | **Vstup** \\ | ||
| Řádek 49: | Řádek 49: | ||
| 7 1 27 \\ | 7 1 27 \\ | ||
| Graf v příkladu 1 je znázorněn na obrázku 1. \\ | Graf v příkladu 1 je znázorněn na obrázku 1. \\ | ||
| - | Příklad 2 \\ | + | == Příklad 2 == |
| **Vstup** \\ | **Vstup** \\ | ||
| Řádek 72: | Řádek 72: | ||
| **Výstup** \\ | **Výstup** \\ | ||
| 6 7 21 \\ | 6 7 21 \\ | ||
| - | **Příklad 3** \\ | + | == Příklad 3 == |
| **Vstup** \\ | **Vstup** \\ | ||
