• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Narciarze OI

0 głosów
511 wizyt
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!
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
pytanie zadane 13 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 1,005 wizyt
pytanie zadane 7 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 326 wizyt
pytanie zadane 20 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

93,424 zapytań

142,421 odpowiedzi

322,646 komentarzy

62,785 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

VMware Cloud PRO - przenieś swoją infrastrukturę IT do chmury
...