2015 PAL zkouška - předtermín 15.12.

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.

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ů.

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.

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.

Vstup
8 13
1
9
4
4
5
3
6
8
0 1
1 2
3 2
4 3
5 4
6 5
6 7
7 0
7 1
3 1
5 3
5 7
0 4
Výstup
7 1 27
Graf v příkladu 1 je znázorněn na obrázku 1.

Vstup
8 9
5
5
20
7
5
5
7
7
2 1
1 0
1 5
0 4
4 5
2 3
3 7
6 3
6 7
Výstup
6 7 21

Vstup
5 10
10
20
30
40
50
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
Výstup
0 4 150