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!
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 |