Runda 10 [Hard] - Gra na grafie
07.02.2011 - Damian Rusak
Zadanie tygodnia runda 10; kategoria Hard Limit czasowy: 3s; Limit pamięciowy: 128MB Gra na grafieDwóch przyjaciół, X i Y, umówiło się na grę na grafie. Jej zasady są następujące:
Zakładając, że X i Y grają optymalnie (czyli każdy będzie chciał ugrać możliwie najwyższy wynik), który wierzchołek powinien zostać wybrany przez X aby zmaksymalizować jego wynik i ile ten maksymalny wynik będzie wynosił? Wejście: Pierwsza linia wejścia zawiera liczbę przypadków testowych . Każdy przypadek testowy ma następującą postać: Pierwsza linia zawiera jedną liczbę naturalną - liczbę wierzchołków grafu (). W kolejnych liniach dla od do znajduje się po liczb całkowitych z przedziału . -ta dodatnia liczba w -tym wierszy oznacza koszt krawędzi z -tego do -tego wierzchołka. Jeśli ta liczba to , krawędź nie istnieje. Jeśli to zawsze liczbą tą jest . Wyjście: Wyjście dla każdego przypadku testowego powinno składać się z dwóch linii. W pierwszej należy wypisać - numer wierzchołka, którego wybór na wierzchołek startowy zmaksymalizuje wynik gracza X. W kolejnej linii należy wypisać ten maksymalny możliwy do uzyskania wynik. Jeśli kilka wierzchołków oferuje ten sam, najlepszy wynik, należy wypisać ten o najmniejszym numerze. Przykład: Wejście: 2 5 0 5 0 2 0 3 0 3 6 1 0 0 0 0 0 0 0 1 0 3 0 0 1 0 0 6 0 9 7 0 0 1 8 0 6 3 0 0 7 7 0 6 0 3 4 3 0 0 0 2 7 5 0 4 0 9 1 0 1 9 0 0 Wyjście: 2 4 1 7
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
(1 ocena) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com