Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 4 ] 
Awans 
Autor Wiadomość
Gwiazda 2Gwiazda 2

Dołączył(a): 21 lis 2009, o 08:16
Posty: 16
Post Awans
Pochwali się ktoś rozwiązaniem za 10 pkt? Spędziłem nad tym zadaniem wczorajszy wieczór, trochę szkoda, że tylko 2/10 ;)

Moim pomysłem było skojarzenie grafu dwudzielnego. Najpierw kojarzyłem pracowników, których muszę zatrudnić, a potem miejsca, które muszą być obstawione.

Przy konstruowaniu ścieżek rozszerzających podczas 2 kojarzenia zauważyłem, że ścieżkę możemy kończyć na pracowniku, który pracuje na nieobowiązkowym stanowisku.

Jeżeli w którymś miejscu ścieżka rozszerzająca nie mogła być skonstruowana program kończył się wynikiem -1.

Swoją drogą podobnym problemem jest 'problem kojarzenia małżeństw' ;)


4 cze 2010, o 22:06
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 24 lis 2009, o 15:59
Posty: 47
Post Re: Awans
To było ciężkie zadanie, o ile myślałem, że jak prze konwertuję wejście, na stanowiska które muszą być zajęte i możliwych kandydatów na nie, oraz na pracowników którzy muszą zostać zatrudnieni i możliwe stanowiska dla każdego z nich, to dalej pójdzie trochę lepiej, lecz zaplątałem się tylko na amen, czekam z niecierpliwością na wyjaśnienie organizatorów.


4 cze 2010, o 22:16
Zobacz profil
Gwiazda 2Gwiazda 2
Avatar użytkownika

Dołączył(a): 17 lis 2009, o 13:15
Posty: 59
Post Re: Awans
Ja się pochwale :D

Więc tak: graf w zadaniu jest grafem dwudzielnym. Zachodzi taka własność:
Graf jest dwudzielny <=> Wszystkie cykle w grafie są parzyste
Całkiem prosto to się udowadnia.

Więc mamy sobie na wejściu pewne dwa skojarzenia, pana Henryka i asystenta jego. Owe dwa skojarzenia tworzą nam pewien podgraf, grafu wejściowego. I jaką właściwość ma każdy wierzchołek tego podgrafu? Otóż stopień każdego wierzchołka <=2 . Oznacza to że podgraf ów składa się z wielu spójnych składowych które mają postać pojedynczego cyklu o parzystej długości, bądź pojedynczej ścieżki. Cykle obrabiamy w ten sposób że wybieramy z nich co drugą krawędź i dodajemy je do wyniku. Pojedyncze ścieżki długości parzystej (parzysta liczba krawędzi) obrabiamy w ten sposób że zauważamy ze w wyniku nie musi się znajdować wierzchołek znajdujący się na jednym z końców, i też wybieramy co drugą krawędź poczynając od tej strony co jest ten potrzebny wierzchołek. Ścieżki nieparzyste obrabiamy tak że wybieramy co drugą krawędź zaczynając od dowolnego końca. No jak widać zawsze się da uzyskać wynik, a podane na wejściu skojarzenia nie były dla picu, tylko się przydawały.


4 cze 2010, o 22:18
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: Awans
Główną trudnością zadania było zauważenie, że podane listy to właśnie są skojarzenia xp.
Potem już szło prosto.
Algorytm był mniej wiecej taki:
Uwzgledniam wszystkie pozycje w planie Henryka.
Dla kaŻdej pozycji z planu asystenta:
Sprawdzam czy danemu pracownikowi zostalo przydzielone stanowisko, jak tak, to nie ruszam, a jak nie, to przydzielam to asystentowe i jeżeli stanowisko przydzielone przez asystenta zostalo wczesniej przydzielone przez Henryka to wyrzucam to Henryka i biorę asystentowe.


4 cze 2010, o 22:34
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 4 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL