Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | jocgraf.in, jocgraf.out | Sursă | Romanian Collegiate Programming Contest 2019 |
| Autor | Valeriu Motroi | Adăugată de |  RCPC2019 •RCPC2019 |
| Timp execuţie pe test | 0.45 sec | Limită de memorie | 32000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Joc pe graf
Cristinel si Alex au gasit un grafuri cu N noduri si M muchii. Pe fiecare dintre muchii si noduri era scris un numar natural.
Vazand aceasta capodopera a matematicii discrete, Alex 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
daca 
![\forall i \in [1, N]](https://www.infoarena.ro/static/images/latex/d9515eb497c3ce1f95924b9a103c46ac_3.5pt.gif "\forall i \in [1, N]")
. Unde S este multimea nodurilor alese de un jucator.
Care este diferenta dintre scorul lui Alex si a lui Cristinel, daca ambii jucatori joaca optim si Alex incepe primul?
Date de intrare
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 
. Pe urmatoarele M linii sunt descrise muchiile ca un triplet u, v, numarul de pe muchie.
Date de ieşire
Î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.
Restricţii
- 0 ≤ N, M ≤ 105
- 0 ≤ Numarul scris pe noduri ≤ 105
- 0 ≤ Numarul scris pe muchii ≤ 105
- 1 ≤ T ≤ 10
Exemplu
| jocgraf.in | jocgraf.out |
|---|---|
| 1 3 3 1 1 1 1 2 1 2 3 1 3 1 1 | 2 |
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.
