Logowanie

Zadanie Narciarze OI

pytanie zadane 22 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 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 2023 przez Whistleroosh Maniak (57,400 p.)

Tak

komentarz 23 marca 2023 przez Whistleroosh Maniak (57,400 p.)

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

komentarz 23 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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

komentarz 23 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 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 2023 przez Whistleroosh Maniak (57,400 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ź 428 wizyt

Zadanie żywopłot, finał XXIII OI

pytanie zadane 13 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

0 głosów

1 odpowiedź 1,005 wizyt

Zadanie Midas finał XXIV OI

pytanie zadane 7 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

0 głosów

1 odpowiedź 326 wizyt

Zadanie Cło 1 etap XV OI

pytanie zadane 20 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

...