Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | easygraph.in, easygraph.out | Sursă | ONIS 2014, Runda 1 |
Autor | Teodor Plop | Adăugată de | |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 12288 kbytes |
Scorul tău | N/A | Dificultate | N/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]. Se dă un număr natural K. Să se găsească şi să se afişeze suma maximă a unui lanţ format din cel mult K noduri distincte. 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 trei numere naturale, N, M şi K, 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
- ... ≤ ... ≤ ...
Exemplu
easygraph.in | easygraph.out |
---|---|
This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...