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

Zadanie Narciarze OI

Aruba Cloud PRO i VPS, Openstack, VMWare, MS Hyper-V
0 głosów
144 wizyt
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!
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
pytanie zadane 13 kwietnia w Algorytmy przez pasjonat_algorytmiki Pasjonat (18,860 p.)
0 głosów
1 odpowiedź 209 wizyt
pytanie zadane 7 kwietnia w Algorytmy przez pasjonat_algorytmiki Pasjonat (18,860 p.)
0 głosów
1 odpowiedź 101 wizyt
pytanie zadane 20 marca w Algorytmy przez pasjonat_algorytmiki Pasjonat (18,860 p.)

91,832 zapytań

140,506 odpowiedzi

316,996 komentarzy

61,163 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...