Hide

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 4 wierzchołkach i 3 krawędziach jest pokazany w wyjaśnieniu pierwszego testu przykładowego.

Ścieżka to ciąg 2 lub więcej wierzchołków taki, że każde dwa kolejne wierzchołki w ciągu są połączone krawędzią. W tym zadaniu będziemy rozważali prote ścieżki, to jest takie, w których żaden wierzchołek nie występuje więcej niż raz. Kolejność wierzchołków ma znaczenie; przykładowo ,,5-6-7”, ,,5-7-6” and ,,7-6-5” to różne ścieżki.

Każdy wierzchołek ma jeden z K kolorów. Twoim zadaniem jest znalezienie liczby różnych (prostych) ścieżek, na których wszystkie wierzchołki mają różne kolory.

Wejście

Pierwszy wiersz wejścia zawiera trzy liczby całkowite: N (liczbę wierzchołków), M (liczbę krawędzi) i K (liczbę kolorów).

Drugi wiersz wejścia zawiera N liczb całkowitych pomiędzy 1 a K – kolory wierzchołków (kolejno dla wierzchołków od 1 do N).

Każdy z kolejnych M wierszy opisuje krawędź i zawiera dwie liczby całkowite a,b (1a,bN,ab) – numery wierzchołków połączonych krawędzią. Między każdą parą wierzchołków będzie co najwyżej jedna krawędź.

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 1018.

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

1N,M100,1K4

2

20

1N,M300000,1K3

3

27

1N,M300000,1K4

4

30

1N,M100000,1K5

Wyjaśnienie do przykładu 1

\includegraphics[width=5cm]{pathsfig.pdf}

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 1.

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
Hide

Please log in to submit a solution to this problem

Log in