Programozás‎ > ‎Feladatok‎ > ‎

Raktár

Egy megye településeiről tudjuk, hogy bármely településről bármelyik másikra pontosan egy útvonalon lehet eljutni. Egy vállalat az összes településen nyit termelő üzemet. Tudjuk, hogy melyik településen van a raktár, ahova az egyes üzemek szállítanák az árut. Ismerjük, hogy melyik településen mennyi terméket gyárthatnak. Az egyes utakon egy nap maximum M mennyiségű termék szállítható. 

Feladat

Írjunk programot, ami kiszámítja, hogy mekkorára kell építeni a raktárt, hogy a lehető legtöbb árut befogadja! 

Bemenet

A bemenet első sorában a települések N száma (1 <= N <= 10000), az utakon szállítható termékek maximális száma (1 <= M <= 100000) és a raktáros település R sorszáma (1 <= R <= N) van. A második sor pontosan N egész számot tartalmaz (egy-egy szóközzel elválasztva), az i. szám az i. településen gyártott áru mennyisége (1 <= mennyiség <= 1000). A következő N-1 sorban két egész szám van (egy-egy szóközzel elválasztva): két település sorszám, amelyek között út van (1 <= A ≠ B <= N).

Kimenet

A kimenet egyetlen sorába a maximális raktárméretet kell írni, ami az üzemekből szállított áruval egy nap megtölthető.

Példa

Bemenet  Kimenet
10 200 2
100 100 50 50 50 100 200 100 50 50
1 2
3 4
4 5
4 2
2 6
6 7
6 8
8 9
10 8
550


Tesztadatok

Címkék

A feladat forrása: NTOITV 2012 3.forduló, 9-10. évfolyam
Algoritmusok: 

megoldás