== include(page="template/taskheader" task_id="tproc") ==
Poveste si cerinta...
Un sistem multiprocesor este alcatuit din $K$ procesoare. Pe acest sistem trebuie executata o aplicatie ce consta din $N$ procese independente, numerotate de la $1$ la $N$. Fiecare proces trebuie executat in totalitate pe unul din cele $K$ procesoare. Deoarece unele procese folosesc date din locatii de memorie total diferite, daca anumite perechi de procese (numite *procese incompatibile*) sunt executate pe acelasi procesor, va aparea fenomenul de 'cache thrashing':http://citeseer.ist.psu.edu/100759.html , care va scadea foarte mult performantele sistemului. Pentru fiecare dintre aceste $P$ perechi de procese incompatibile $(i,j)$ este cunoscuta penalizarea de performanta $pe{~i,j~}$, adusa daca cele $2$ procese sunt executate pe acelasi procesor. Penalizarea de performanta totala este egala cu suma penalizarilor de performanta pentru fiecare pereche de procese incompatibile care sunt executate pe acelasi procesor.
Determinati penalizarea de performanta totala minima posibila pentru executia celor $N$ procese pe cele $K$ procesoare ale sistemului.
In rezolvarea problemei puteti sa va folositi de urmatoarea particularitate a aplicatiei compusa din cele $N$ procese: Procesele sunt organizate in $M$ grupuri, in functie de tipul prelucrarilor pe care le au de realizat. Grupurile sunt numerotate de la $1$ la $M$. Fiecare grup contine *cel mult 8 procese*. Un proces poate face parte din mai multe grupuri. Daca $2$ procese $i$ si $j$ sunt incompatibile, atunci va exista cel putin un grup $X$ din care fac parte atat procesul $i$, cat si procesul $j$. Cele $M$ grupuri sunt organizate intr-o structura arborescenta. Mai exact, exista $M-1$ perechi de grupuri cu proprietatea ca intre cele $2$ grupuri $X$ si $Y$ dintr-o pereche exista referinte reciproce, iar graful format din grupuri ca noduri si perechile de grupuri ca muchii formeaza un *arbore* (graf conex si fara cicluri). Toate grupurile din care face parte un proces $i$ formeaza un subarbore al arborelui grupurilor (acest lucru se datoreaza faptului ca, in cadrul aplicatiei, este necesar sa se poata ajunge prin intermediul referintelor dintre grupuri, de la orice grup din care face parte procesul $i$ la orice alt grup din care face parte procesul $i$). Aceasta ultima proprietate este echivalenta cu urmatoarea: daca un proces $i$ face parte din grupurile $X$ si $Y$, atunci el va face parte din toate grupurile aflate pe drumul unic dintre $X$ si $Y$.
h2. Date de intrare
Fisierul de intrare $tproc.in$ ...
Prima linie a fisierului de intrare $tproc.in$ contine numerele intregi $M$, $N$ si $K$, separate prin cate un spatiu. Urmatoarele $M-1$ linii contin cate $2$ numere intregi $X$ si $Y$, separate printr-un spatiu, reprezentand $2$ grupuri intre care exista o referinta. Urmatoarele $M$ linii descriu alcatuirea fiecarui grup. A $X$-a din aceste $M$ linii reprezinta descrierea grupului cu numarul $X$. Primul numar de pe linie reprezinta numarul $T$ de procese ce fac parte din grupul $X$. Urmatoarele $T$ numere reprezinta numerele celor $T$ procese. Cele $T+1$ numere de pe linie sunt separate prin cate un spatiu. Urmatoarea linie contine numarul intreg $P$ de perechi de procese incompatibile. Urmatoarele $P$ linii contin cate $3$ numere intregi, $i$, $j$ si $pe{~i,j~}$, separate prin cate un spatiu, reprezentand numerele celor $2$ procese incompatibile din cadrul perechii si penalizarea de performanta asociata executiei celor 2 procese pe acelasi procesor.
h2. Date de iesire
In fisierul de iesire $tproc.out$ ...
In fisierul de iesire $tproc.out$ veti afisa penalizarea totala minima posibila pentru executia celor $N$ procese pe cele $K$ procesoare ale sistemului.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ M ≤ 500$
* $1 ≤ N ≤ 500$
* $1 ≤ K ≤ 8$
* Fiecare grup va contine intre 0 si 8 procese (inclusiv).
* Un proces poate face parte din oricate grupuri (cel putin unul).
* $0 ≤ P ≤ 3000$
* $0 ≤ pe{~i,j~} ≤ 1000$
h2. Exemplu
table(example). |_. tproc.in |_. tproc.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|6 9 3
1 3
6 3
4 3
5 3
2 1
7 1 2 3 4 5 7 9
5 1 2 3 5 9
8 1 2 3 4 6 7 8 9
5 2 4 6 7 8
5 2 4 6 7 8
6 1 4 6 7 8 9
22
1 2 703
1 3 485
1 4 384
1 5 216
1 7 670
1 9 410
2 3 789
2 4 977
2 6 210
2 7 856
2 9 610
3 4 780
3 9 453
4 6 149
4 8 528
4 9 85
5 9 949
6 7 754
6 8 457
7 8 204
7 9 827
8 9 700
|937|
|2 10 2
1 2
6 1 2 3 4 5 6
6 1 2 7 8 9 10
12
1 3 1
3 4 1
4 2 1
3 5 1
5 6 1
6 1 1
1 7 1
1 8 1
1 9 1
1 10 1
2 7 1
2 8 1
2 9 1
2 10 1
|1|
h3. Explicatie
...
In primul exemplu, o solutie optima a repartizarii celor $9$ procese pe cele $3$ procesoare este urmatoarea (al i-lea numar din secventa indica pe ce procesor este executat procesul $i$): $2 2 3 1 3 1 3 2 1$.
In al doilea exemplu, o solutie optima a repartizarii celor $10$ procese pe cele $2$ procesoare este urmatoarea: $1 1 2 1 1 2 2 2 2 2$.
== include(page="template/taskfooter" task_id="tproc") ==
== include(page="template/taskfooter" task_id="tproc") ==
