Witam serdecznie.
Przygotowuje się do olimpiady z informatyki i z tegoż powodu robię sobie różne zadania archiwalne.
Natknąłem się na takie zadanie: http://www.sendspace.pl/file/357157d5764c145f966d26b
Z tego co wiem, zadanie to ma związek z grafami. Rozumiem pytanie i treść zadania, ale nie mam na niego za bardzo pomysłu (miałem nawet jeden, ale zawiły i prawdopodobnie za wolny). Czy byłby ktoś tak miły i dał mi jakąś wskazówkę, link do zagadnienia, jak mogę sobie z tym zadaniem poradzić? (oczywiście nie oczekuje od Was żadnego gotowego kodu)
- Rejestracja:ponad 13 lat
- Ostatnio:ponad 10 lat
- Postów:31
0
C++ 
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
2
Jak masz N-1 wierszy to masz minimalny graf rozpinający. Więc dla każdego więzła zwykłym BFS (http://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz) przechodzisz całość licząc ile razy musiałeś przejść w kierunku przeciwnym. Wyświetlasz minimalną wartość dla węzła.
Strukturą najlepiej tablica N elementów (węzły) zawierająca dwie listy (krawędzie) węzłów wchodzących i wychodzących.
0
Ale jak rozumieć dla każdego wierzchołka?
A przeczytałeś przynajmniej pierwsze zdanie z linku?
0
_13th_Dragon napisał(a):
Jak masz N-1 wierszy to masz minimalny graf rozpinający. Więc dla każdego więzła zwykłym BFS (http://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz) przechodzisz całość licząc ile razy musiałeś przejść w kierunku przeciwnym. Wyświetlasz minimalną wartość dla węzła.
Strukturą najlepiej tablica N elementów (węzły) zawierająca dwie listy (krawędzie) węzłów wchodzących i wychodzących.
Takie rozwiązanie nie będzie wystarczająco szybkie (na zawodach nie dostałoby za wiele punktów).
W powyższym rozwiązaniu złożoność będzie O(n^2), co dla max(n) = 100000 jest o wiele za dużo.
Wzorcówka musi być rzędu O(n) | O(nlogn).
1
Ok, rozwiązanie liniowe.
Bierzemy którykolwiek wierzchołek(np. nr 1), zapuszczamy z niego BFS-a(link wyżej) i zliczamy ile napotkaliśmy krawędzi przeciwnych(tych które byłoby trzeba zmienić).
Zapamiętujemy tę wartość w dodatkowej zmiennej(powiedzmy "koszt") dla wierzchołka nr 1 (musimy posiadać taką dodatkową zmienną dla każdego wierzchołka).
Teraz startujemy ponownie BFS-em z wierzchołka nr 1, jednak tym razem napotkanym wierzchołkom przypisujemy koszty.
Koszt dla wierzchołka = koszt w wierzchołku z którego przyszliśmy+: -1 jeżeli przyszliśmy "pod prąd", +1 w przeciwnym wypadku.
Odpowiedź to najmniejsza wartość ze wszystkich kosztów.
Wydaje mi się, że takie rozumowanie jest poprawne.
- Rejestracja:ponad 13 lat
- Ostatnio:ponad 10 lat
- Postów:31
0
Może to zabrzmi dziwnie, bo w takiej sytuacji każdy może tak powiedzieć, ale ten mój zawiły pomysł (o którym wspomniałem na początku) właśnie tak wyglądał ;) Tylko nie umiałem tego napisać, bo nie znałem BFS-a. Później dodatkowo przyszła mi myśl, że gdyby się uprzeć, to można by całość obliczyć przy jednym zapuszczeniu BFS-a. Po prostu równolegle do jednej tablicy spisywałby, czy jest "pod prąd", czy nie, a przy okazji obliczałby ilość zmian, których trzeba dokonać dla wierzchołka nr 1 żeby stał się bazą.
Dzięki wszystkim za odpowiedzi.