 |
Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Fidel
żul
Dołączył: 19 Lis 2005
Posty: 649
Przeczytał: 0 tematów
Skąd: Kraków
|
 Wysłany: Pią 13:43, 07 Lis 2008 Temat postu: ASD |
|
|
Moze ktos z algorytmikow ma chec wymyslic jak zrobic zadanka alla ASD :>
| Kod: | TEMAT
W odległym państwie, pewna partia postanowiła w ramach antyrządowego protestu zablokować najważniejsze drogi w państwie. Przewodniczący partii - Andrew L. - wyznaczył wstępny plan, dróg, na których powinny powstać blokady, jak również mianował w każdym mieście przewodniczącego lokalnego oddziału partii. Każdy oddział lokalny miał czuwać nad stanem blokady wszystkich dróg wjazdowych/wyjazdowych z miasta.
Andrew L. ustalił również następujące zasady strajku: "Jeśli zadzwonię do któregoś z lokalnych przewodniczących, wtedy on będzie musiał <<puścić sygnał>> każdemu z szefów blokad, którzy kontrolują ruch na drodze łączącej miasto z sąsiednimi. Szef blokady, jeśli dostanie sygnał tylko od jednego przewodniczącego, zobowiązany będzie do zmiany stanu blokady - tzn. jeśli droga była zablokowana, ma ją odblokować; jeśli odblokowana - zablokować. Jeśli otrzyma dwa sygnały lub nie otrzyma sygnału wcale - ma pozostawać w gotowości, ale stanu drogi nie zmieniać."
Andrew L. objął osobiście przewodnictwo w stolicy - i ze względu na swoją pozycję, nie zamierza kontaktować się z działaczami terenowymi na drogach wlotowych do stolicy.
Czy Andrew L. jest w stanie zablokować cały kraj kontaktując się wyłącznie z lokalnymi przewodniczącymi partii? Jakie telefony musi Andrew L. wykonać (zgodnie z kolejnością w spisie kontaktów), aby wszystkie drogi w kraju zostały zablokowane ?
WEJŚCIE
W pierwszej linii wejścia znajduje się liczba całkowita z — liczba zestawów danych (liczba wariantów strajku, które obejmują różną powierzchnię kraju). W kolejnych liniach znajdują się zestawy (warianty), z których każdy jest następującej postaci: pierwsza linia zestawu zawiera dwie liczby naturalne n i m (2<=n<=50000, 1<=m<=500000), oznaczające odpowiednio liczbę miast oraz liczbę wszystkich dróg. W dalszych m liniach znajdują się po dwie liczby naturalne ai, bi (1<=ai, bi<=n) — numery miast, które łączy i-ta droga oraz jeden znak + lub - oznaczający odpowiednio początkowy stan: obecność blokady lub jej brak. Miasto o numerze 1 to stolica kraju, w której zarządza osobiście Andrew L.
Żadna droga nie łączy miasta z samym sobą. Droga jest blokowana zawsze dla ruchu w obydwu kierunkach. Pomiędzy dwoma miastami może być tylko i wyłącznie jedna droga dojazdowa. Z każdego miasta można dojechać do dowolnego innego.
WYJŚCIE
Dla każdego zestawu należy wypisać jedno słowo NIE, jeśli niezależnie od kolejności wykonanych telefonów, Andrew L. nie uda się zablokować wszystkich dróg w kraju lub ciąg liczb oddzielonych spacjami — kolejne pozycje na liście telefonów, na które Andrew L. musi zadzwonić, aby osiągnąć swój cel. Numery należy wypisać w porządku rosnącym, liczba
1 (czyli telefon samego przewodniczącego) nie może się wśród nich pojawić.
PRZYKŁAD
Przykładowe wejście
1
4 4
1 2 -
2 3 +
3 4 -
4 1 +
Przykładowe wyjście
2 3 |
|
|
| Powrót do góry |
|
 |
|
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Spectro
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów
Skąd: Kurdwanów
|
| Wysłany: Pią 14:42, 07 Lis 2008 Temat postu: Re: ASD |
|
|
To jest dokładnie to zadanie:
[link widoczny dla zalogowanych]
Rozwiązanie to zwykły DFS z miasta 1, który przy przeglądaniu kolejnych krawędzi sprawdza, czy jest na niej blokada bądź nie. Jeśli nie ma - oznacza wierzchołek, do którego wchodzimy naszą krawędzią, że został zmieniony i faktycznie zmieniamy stan sąsiadujących z nim ulic. Po DFSie sprawdzamy, czy każda ulica jest zablokowana i jeżeli tak, to wypisujemy oznaczone wierzchołki.
Ostatnio zmieniony przez Spectro dnia Pią 14:43, 07 Lis 2008, w całości zmieniany 1 raz
|
|
| Powrót do góry |
|
|
|
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
|
fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Szukaj
Użytkownicy
Grupy
Galerie
Rejestracja
Zaloguj się, by sprawdzić wiadomości
Zaloguj
