Diferente pentru problema/easygraph intre reviziile #18 si #1

Diferente intre titluri:

Easygraph
easygraph

Diferente intre continut:

== include(page="template/taskheader" task_id="easygraph") ==
După cum spune şi numele problemei, aceasta este o problemă *simplă* cu grafuri. Iar cu ocazia sărbătorilor de iarnă, Moş Crăciun s-a gândit să scurteze enunţul acestei probleme şi să vă premieze cu $100$ puncte dacă o rezolvaţi corect!
 
Se dă un graf orientat aciclic cu $N$ noduri şi $M$ muchii. Fiecare nod $i$ are o valoare $v[i]$. Să se găsească şi să se afişeze suma maximă a unui lanţ din graf. Suma unui lanţ este suma valorilor nodurilor conţinute de acesta.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $easygraph.in$ conţine pe prima linie numărul de teste, $T$. În continuare, pentru fiecare test, se vor găsi pe prima linie două numere naturale $N$ şi $M$, având semnificaţia din enunţ. Pe cea de-a doua linie, se vor găsi $N$ numere întregi, elementele vectorului $v[i]$. Pe următoarele $M$ linii se vor găsi câte două numere $x$ şi $y$, cu semnificaţia că există un arc de la nodul $x$ la nodul $y$.
Fişierul de intrare $easygraph.in$ ...
h2. Date de ieşire
În fişierul de ieşire $easygraph.out$ se vor găsi $T$ linii, pe linia $i$ găsindu-se răspunsul pentru testul $i$.
În fişierul de ieşire $easygraph.out$ ...
h2. Restricţii
* $T = 20$
* $1 ≤ N ≤ 15.000$
* $1 ≤ M ≤ 30.000$
* $-10^6^ ≤ v[i] ≤ 10^6^$
* $Pot exista mai multe arce între aceleaşi noduri X şi Y.$
* $Lanţul găsit de sumă maximă trebuie să conţină cel puţin 1 nod.$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. easygraph.in |_. easygraph.out |
| 1
4 3
-3 -1 15 5
1 3
3 2
2 4
| 19
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
h3. Explicaţie
Lanţul de sumă maximă este: $3$ -> $2$ -> $4$. Suma lanţului este $19$.
...
== include(page="template/taskfooter" task_id="easygraph") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

9416