Poveste şi cerinţă...
Se da un graf orientat cu N noduri. Din fiecare nod pleaca exact K arce de costuri 1,2...K (Cate un arc de fiecare cost). Pot exista arce multiple intre 2 noduri, si arce de la un nod la acelasi nod. Un drum este o succestiune de arce...care poate trece prin acelasi nod si prin aceeasi muchie de mai multe ori. Costul unui drum de lungime L este calculat astfel: Costul primului arc inmultit cu (K+1)^0^, adunat cu costul celui de-al doilea arc inmultit cu (K+1)^1^,... adunat cu costul celui de-al L-lea arc inmultit cu (K+1)^L-1^.
!?graph.png!
Spre exemplu, pentru drumul de la 1 la 4 din graful din figura, costul acestui drum
pentru K = 3 este :
3*4 0 + 1*4 1 + 2*4 2 = 39
Nodurile sunt colorate in 2 culori: alb si
negru. Exista M noduri albe, iar restul sunt
negre.
Doua noduri sunt simetrice daca pentru un orice cost S posibil, drumurile de cost
exact S care pleaca din cele doua noduri ajung in noduri de aceeasi culoare. (Daca
nodurile A si B sunt simetrice, atunci nu exista un drum de cost S care pleaca din
nodul A si un drum de acelasi cost din nodul B care sa ajunga in doua noduri de
culoari diferite)
O multime de noduri s.n. perfecta, daca oricum am alege doua noduri din aceasta
multime, ele sunt simetrice.
O multime se numeste perfecta de cardinal maxim daca oricum am adauga un alt nod
la multimea respectiva, aceasta nu mai indeplineste conditia de a fi perfecta.
Scopul vostru este sa afisati toate multimile perfecte de cardinal maxim. Afisati
multimile in ordine lexicografica, cate una pe rand. (in cadrul unei multimi, elementele
trebuie sortate in ordine crescatoare).
Spre exemplu, pentru drumul de la 1 la 4 din graful din figura, costul acestui drum pentru K = 3 este: 3*4^0^+1*4^1^+2*4^2^=39
!problema/escape?graph2.png!
Nodurile sunt colorate in 2 culori: alb si negru. Exista M noduri albe, iar restul sunt negre.
Doua noduri sunt *simetrice* daca pentru un orice cost S posibil, drumurile de cost exact S care pleaca din cele doua noduri ajung in noduri de aceeasi culoare. (Daca nodurile A si B sunt simetrice, atunci nu exista un drum de cost S care pleaca din nodul A si un drum de acelasi cost din nodul B care sa ajunga in doua noduri de culoari diferite)
O multime de noduri se numeste *perfecta*, daca oricum am alege doua noduri din aceasta multime, ele sunt simetrice.
O multime se numeste *perfecta de cardinal maxim* daca oricum am adauga un alt nod la multimea respectiva, aceasta nu mai indeplineste conditia de a fi perfecta.
Scopul vostru este sa afisati toate multimile perfecte de cardinal maxim. Afisati multimile in ordine lexicografica, cate una pe rand. (in cadrul unei multimi, elementele trebuie sortate in ordine crescatoare).
h2. Date de intrare
Fişierul de intrare $escape.in$ ...
In fişierul de intrare $escape.in$, pe prime linie se vor gasi 3 numere naturale: N, M si K, in aceasta ordine.
Pe urmatoare linie se vor gasi M numere distincte, reprezentand indicii nodurilor albe din graf.
Urmeaza o matrice A cu N linii si K coloane unde A{~i,j~} reprezinta un arc care pleaca din nodul i si ajunge in nodul A{~i,j~} si are costul j.
h2. Date de ieşire
În fişierul de ieşire $escape.out$ ...
În fişierul de ieşire $escape.out$ afisati, in ordine lexicografica, cate una pe fiecare linie, toate multimile perfecte de cardinal maxim (elementele din cadrul multimilor vor fi sortate in ordine crescatoare)
h2. Restricţii
* $... ≤ ... ≤ ...$
30 pct:
* $1 ≤ K ≤ 10$
* $1 ≤ M ≤ N ≤ 15$
* $1 ≤ A{~i,j~} ≤ N$
60 pct:
* $1 ≤ K ≤ 30$
* $1 ≤ M ≤ N ≤ 50$
* $1 ≤ A{~i,j~} ≤ N$
100 pct:
* $1 ≤ K ≤ 50$
* $1 ≤ M ≤ N ≤ 500$
* $1 ≤ A{~i,j~} ≤ N$
h2. Exemplu
table(example). |_. escape.in |_. escape.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 1 2
3
2 3
1 3
3 3
| 1 2
3
|
h3. Explicaţie
