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

Joc pe graf

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
$sum(S) + sum(u_i, v_i)$ daca $u_i, v_i \in S$ $\forall i \in [1, N]$ . 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.

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 $x_1, x_2, ..., x_N$ . 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 ≤ 10⁵
0 ≤ Numarul scris pe noduri ≤ 10⁵
0 ≤ Numarul scris pe muchii ≤ 10⁵
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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta