Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-12-10 23:25:44.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:easygraph.in, easygraph.outSursăONIS 2014, Runda 1
AutorTeodor PlopAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.3 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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 naturale, 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ă o muchie orientată de la nodul x la nodul y.

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.

Restricţii

  • T = 10
  • 1 ≤ N ≤ 1.000
  • 1 ≤ M ≤ 2.000
  • $-106 ≤ v[i] &le 106;

Exemplu

easygraph.ineasygraph.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?