Logowanie

Zadanie Narciarze OI

pytanie zadane 22 marca w Algorytmy przez pasjonat_algorytmiki Pasjonat (18,860 p.)

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/Yb04CMWb5dkJbro4Hhmexx_E/site/?key=statement
Myślałem, żeby póścić BFS-a od jedynki, żeby uporządkować je w kolejności, gdy w momencie przetwarzania wierzchołka x, mam przetwożonych wszystkich jego poprzedników, ale to chyba nie zadziała.

Z góry dziękuję za pomoc i poświęcony czas!

Pokaż 6 poprzednich komentarzy

komentarz 22 marca przez Whistleroosh Maniak (55,720 p.)

Tak

komentarz 23 marca przez Whistleroosh Maniak (55,720 p.)

Spojrzałem jeszcze raz na treść i pominelismy ważną kwestię. Ten graf jest planarny

komentarz 23 marca przez pasjonat_algorytmiki Pasjonat (18,860 p.)

Chyba zachłan wejdzie, gdzie będę szedł DFS-em najbardziej lewą ścieżką. Ale nie mam dowodu

komentarz 23 marca przez pasjonat_algorytmiki Pasjonat (18,860 p.)

Bo te przepływy to o ile dobrze rozumiem, to mają O(N^3), czyli zawolno. jak N <= 5000 w tym zadaniu.

komentarz 23 marca przez Whistleroosh Maniak (55,720 p.)

Zachłan wejdzie. Gdyby graf nie był planarny to by nie zadziałało

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów

1 odpowiedź 148 wizyt

Zadanie żywopłot, finał XXIII OI

pytanie zadane 13 kwietnia w Algorytmy przez pasjonat_algorytmiki Pasjonat (18,860 p.)

0 głosów

1 odpowiedź 209 wizyt

Zadanie Midas finał XXIV OI

pytanie zadane 7 kwietnia w Algorytmy przez pasjonat_algorytmiki Pasjonat (18,860 p.)

0 głosów

1 odpowiedź 101 wizyt

Zadanie Cło 1 etap XV OI

pytanie zadane 20 marca w Algorytmy przez pasjonat_algorytmiki Pasjonat (18,860 p.)

...