Problem C
Ścieżki
Languages
de
en
et
is
ja
lt
lv
no
pl
ru
sv
Graf to struktura matematyczna złożona ze zbioru
wierzchołków i zbioru krawędzi, każda krawędź
łączy dwa wierzchołki. Przykładowy graf o
Ścieżka to ciąg
Każdy wierzchołek ma jeden z
Wejście
Pierwszy wiersz wejścia zawiera trzy liczby całkowite:
Drugi wiersz wejścia zawiera
Każdy z kolejnych
Wyjście
Na wyjście wypisz pojedynczą liczbę całkowitą – liczbę
ścieżek, na których wszystkie wierzchołki mają parami różne
kolory. Wynik nie przekroczy
Ograniczenia
Zestaw testów dzieli się na kilka grup, każda jest warta pewną liczbę punktów. Każda grupa składa się z jednego bądź większej liczby testów. Aby otrzymać punkty za daną grupę, Twoje rozwiązanie musi przejść wszystkie testy z tej grupy. Ostateczny wynik za zadanie jest liczony jako maksymalny wynik z pojedynczych zgłoszeń.
Grupa |
Punkty |
Limity |
1 |
23 |
|
2 |
20 |
|
3 |
27 |
|
4 |
30 |
|
Wyjaśnienie do przykładu 1
Rysunek przedstawia graf z pierwszego testu przykładowego, każdy wierzchołek ma kolor biały (kolor 1), szary (kolor 2) lub czarny (kolor 3). Jest 10 ścieżek, na których wszystkie wierzchołki mają różne kolory: ,,1-2”, ,,2-1”, ,,2-3”, ,,3-2”, ,,2-4”, ,,4-2”, ,,1-2-4”, ,,4-2-1”, ,,3-2-4” oraz ,,4-2-3”.
,,1” nie jest poprawną ścieżką,
ponieważ zawiera tylko jeden wierzchołek, jak również
,,1-2-3”, ponieważ zawiera dwa
wierzchołki o kolorze
Przykładowe wejście 1 | Przykładowe wyjście 1 |
---|---|
4 3 3 1 2 1 3 1 2 2 3 4 2 |
10 |
Przykładowe wejście 2 | Przykładowe wyjście 2 |
---|---|
9 11 4 1 2 3 4 1 2 1 2 2 1 2 1 3 2 3 2 4 3 6 6 2 6 5 4 3 4 5 7 8 9 8 |
70 |