Runda 10 [Hard] - Gra na grafie

07.02.2011 - Damian Rusak
TrudnośćTrudność

Zadanie tygodnia

runda 10; kategoria Hard

Limit czasowy: 3s; Limit pamięciowy: 128MB


Gra na grafie

Dwóch przyjaciół, X i Y, umówiło się na grę na grafie. Jej zasady są następujące: 

 

  1. Gra rozgrywa się na skierowanym grafie z wagami na krawędziach.
  2. X wybiera startowy wierzchołek grafu S i ustawia na nim czarny pionek.
  3. Gracze na przemian (poczynając od X) wykonują ruch w następujący sposób:
    • Niech A będzie wierzchołkiem, na którym znajduje się czarny pionek.
    • Gracz może przestawić czarny pionek na pole B, pod warunkiem, że A jest połączone z B krawędzią i na B nie stoi biały pionek.
    • Jeśli gracz przesunie czarny pionek z A na B, na polu A ustawia biały pionek.
    • Gracz zdobywa tyle punktów, ile wynosi waga krawędzi z A do B.
    • Jeśli nie można wykonać żadnego ruchu, gra kończy się.
  4. Wynikiem gry dla każdego gracza jest różnica pomiędzy zdobytymi przez niego punktami, a liczbą punktów zdobytą przez przeciwnika.

 

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 $ t $. Każdy przypadek testowy ma następującą postać:

Pierwsza linia zawiera jedną liczbę naturalną $ n $ - liczbę wierzchołków grafu ($ 2 \leq n \leq 20 $). W kolejnych $ n $ liniach dla $ i $ od $ 1 $ do $ n $ znajduje się po $ n $ liczb całkowitych z przedziału $ \left[0,10^{6}\right] $. $ j $-ta dodatnia liczba w $ i $-tym wierszy oznacza koszt krawędzi z $ i $-tego do $ j $-tego wierzchołka. Jeśli ta liczba to $ 0 $, krawędź nie istnieje. Jeśli $ j = i $ to zawsze liczbą tą jest $ 0 $.

Wyjście:

Wyjście dla każdego przypadku testowego powinno składać się z dwóch linii. W pierwszej należy wypisać $ S $ - 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.
PozycjaImię i nazwiskoWynikCzasGra na grafie2
1Piotr Bejda10107:48:1610
2Damian Straszak10271:21:2410
3Kamil Dębowski10633:02:4910
4Witold Długosz101263:26:5610
5Bartek Dudek8149:21:368
6Przemysław Derengowski8175:59:328
7Adam Tażyk4153:00:504
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com