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

Zadanie Narciarze OI

VPS Starter Arubacloud
0 głosów
256 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 (56,900 p.)
Tak
komentarz 23 marca 2023 przez Whistleroosh Maniak (56,900 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 (56,900 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ź 213 wizyt
pytanie zadane 13 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 517 wizyt
pytanie zadane 7 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 154 wizyt
pytanie zadane 20 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,453 zapytań

141,262 odpowiedzi

319,086 komentarzy

61,854 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.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...