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 î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.

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 = 20
  • 1 ≤ N ≤ 15.000
  • 1 ≤ M ≤ 30.000
  • -106 ≤ v[i] ≤ 106
  • 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.

Exemplu

easygraph.ineasygraph.out
1
4 3
-3 -1 15 5
1 3
3 2
2 4
19

Explicaţie

Lanţul de sumă maximă este: 3 -> 2 -> 4. Suma lanţului este 19.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content