Diferente pentru problema/jocgraf intre reviziile #2 si #21

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="jocgraf") ==
Poveste şi cerinţă...
Cristinel si Alexei au gasit un graf neorientat cu *N* noduri si *M* muchii. Pe fiecare dintre muchii si noduri era scris un numar natural.
Vazand aceasta capodopera a matematicii discrete, Alexei a propus sa se joace un joc pe acel graf.
Jocul se joaca alternativ, fiecare trebuie sa aleaga un nod care nu a mai fost ales, pana se termina graful.
La final, punctajul fiecarui jucator este suma numerelor de pe nodurile alese si a muchiilor
a caror varfuri sunt in multimea nodurilor alese de acel jucator. Formal, scorul unui jucator este
<tex>sum(S) + sum(u_i, v_i) </tex> daca <tex>u_i, v_i \in S </tex> <tex>\forall i \in [1, N]</tex>. Unde *S* este multimea nodurilor alese de un jucator.
Care este diferenta dintre scorurile jucatorilor, daca ambii jucatori joaca optim si Alexei incepe primul?
Precizare: Joc optim inseamna maximizarea diferentei de scor.
h2. Date de intrare
Fişierul de intrare $jocgraf.in$ ...
Fişierul de intrare $jocgraf.in$ contine pe prima linie numarul de teste *T*. Urmeaza apoi descrierea fiecarui test care incepe cu *N* si *M*, numarul de noduri si respectiv muchii a grafului. Pe urmatoare linie sunt numerele scrise pe fiecare nod <tex>x_1, x_2, ..., x_N </tex>. Pe urmatoarele *M* linii sunt descrise muchiile ca un triplet *u*, *v*, *numarul de pe muchie*.
h2. Date de ieşire
În fişierul de ieşire $jocgraf.out$ ...
În fişierul de ieşire $jocgraf.out$ va contine *T* linii cu raspunsul corect (sunt sigur de asta) pentru fiecare dintre cele *T* teste.
h2. Restricţii
* $... &le; ... &le; ...$
* $0 &le; N, M &le; 10^5^$
* $0 &le; Numarul scris pe noduri &le; 10^5^$
* $0 &le; Numarul scris pe muchii &le; 10^5^$
* $1 &le; T &le; 10$
h2. Exemplu
table(example). |_. jocgraf.in |_. jocgraf.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 1
  3 3
  1 1 1
  1 2 1
  2 3 1
  3 1 1
| 2
 
|
h3. Explicaţie
...
Pentru ca toate nodurile si muchiile au costul 1, nu conteaza ce noduri o sa aleaga fiecare, diferenta de scor oricum o sa fie 2.
== include(page="template/taskfooter" task_id="jocgraf") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.