| Fişierul intrare/ieşire: | pastrafaceri.in, pastrafaceri.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 18 |
| Autor | Chichirim George | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.8 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/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
- -106 ≤ vali ≤ 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.in | pastrafaceri.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.
