Fişierul intrare/ieşire:pastrafaceri.in, pastrafaceri.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.8 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pastrama si Afacerile

Tara in care traieste afaceristul Sorin Pastrama contine N orase, unite intre ele prin M drumuri bidirectionale. Aceasta tara este putin cam dubiosa deoarece ea contine numai cicluri de lungime impara. Cu alte cuvinte, tara este un graf cu N noduri si M muchii, conex, care are numai cicluri de lungime impara. Bineinteles, Pastrama are cate o afacere in fiecare oras. Ca orice afaceri, unele sunt profitabile, altele nu. Asa ca vom nota "profitul" afacerii din orasul i cu un numar intreg vali.

Cerinta

S-ar putea ca pastrarea tuturor afacerilor sa nu-i aduca niciun profit lui Pastrama, asa ca el va roaga sa-l ajutati si sa ii spuneti care e valoarea maxima pe care o poate obtine daca el poate alege sa pastreze o submultime de afaceri care sunt conectate intre ele. Cu alte cuvinte, el doreste sa afle care este suma maxima a valorilor unui subgraf conex.

Date de intrare

Fişierul de intrare pastrafaceri.in contine pe prima linie numerele naturale N si M, cu semnificatiile din enunt. Pe urmatoarea linie se afla N numere intregi, a i-a fiind valoarea nodului i. Pe urmatoarele M linii se afla cate doua numere naturale x si y, ce reprezinta ca avem o muchie bidirectionala intre nodurile x si y.

Date de ieşire

În fişierul de ieşire pastrafaceri.out se va afla un numar natural care reprezinta valoarea maxima care poate fi obtinuta.

Restricţii

  • 1 ≤ N ≤ 3 * 105
  • 1 ≤ M ≤ 4 * 105
  • -106vali ≤ 106
  • Un ciclu este orice traseu care pleaca dintr-un nod, ajunge in acelasi nod, si trece prin fiecare muchie cel mult o data. Lungimea acestuia este numarul de muchii parcurse (asta inseamna ca se poate trece printr-un nod de mai multe ori dar nu printr-o muchie)
  • Graful dat va contine numai cicluri de lungime impara
  • Se poate sa nu se aleaga niciun nod, valoarea acestei solutii fiind 0
  • Atentie la numele fisierului de intrare - pastrafaceri.in in loc de pastramasiafacerile.in
  • Atentie la numele fisierului de iesire - pastrafaceri.out in loc de pastramasiafacerile.out
  • Buzunarul lui Sorin Pastrama vorbeste orice limba isi doreste

Exemplu

pastrafaceri.inpastrafaceri.out
4 4
-1 3 -2 4
1 2
2 3
3 1
1 4
6

Explicaţie

Alegem nodurile 1, 2 si 4 care au suma valorilor egala cu 6.
Se putea obtine o valoarea mai mare selectand doar nodurile 2 si 4, dar acestea nu sunt conectate intre ele.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?