Runda 4 - Diamenty w kopalni

12.10.2009 - Damian Rusak
TrudnośćTrudność

 Zawody stałe, runda 4

Limit czasowy : 1s ; Limit pamięciowy: 32 MB

 


Diamenty w kopalni

 

W Górach Kaczawskich znaleziono niedawno bogate złoża. Na szczęście nie chodzi o węgiel brunatny - tym razem to diamenty, ukryte w twardej skale. Badacze odkryli w okolicach złoża system podziemnych tuneli, naturalnego pochodzenia. Chcą pobrać próbki diamentów, aby zadecydować, czy warto eksploatować złoże. Zrozumiałym jest, że chcą znaleźć jak najwięcej kamieni. Sieć tuneli zaczyna się od wejścia - jaskini - i składa się z podziemnych grot, połączonych korytarzami. Każdy korytarz prowadzi zawsze do groty znajdującej się niżej, niemożliwy jest więc powrót do groty, z której się przybyło. Z jednej groty może prowadzić w dół dowolna liczba tuneli, może nie prowadzić też żaden. Każde dwie groty są połączone co najwyżej jednym bezpośrednim tunelem. Tunele nie przecinają się, ale mogą biec pod lub nad sobą. Groty oznaczono kolejnymi liczbami naturalnymi, jaskinia zaś posiada numer 0. W każdej z grot znajduje się nieujemna liczba diamentów. Badacze dysponują niewielkimi środkami i chcieliby zejść tunelami tylko raz, na dowolną głębokość. Znając plan tuneli i ilość diamentów w każdej z grot, pomóż im obliczyć, ile najwięcej diamentów do badań mogą zebrać.


Zadanie:

Dla danego planu połączeń pomiędzy grotami w kopalni, Twój program powinien podać największą możliwą liczbę diamentów, które można zebrać na dowolnej trasie w głąb systemu tuneli, gdy startuje się z jaskini. Twój program powinien wczytywać dane na standardowe wejście i wypisywać odpowiedź na standardowe wyjście.


Wejście:

W pierwszej linii wejścia znajdują się dwie liczby całkowite n i m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000), oznaczające kolejno ilość grot i ilość tuneli. W następnej linii znajduje się n liczb ci (0 ≤ ci ≤ 1 000), oznaczających ilość diamentów w i-tej grocie. W kolejnych m liniach znajdują się pary liczb aj bj (0 ≤ aj ≤ n, 0 < bj ≤ n) oznaczające numery grot stanowiących początek i koniec j-tego tunelu.

 

Wyjście:

Wyjście powinno składać się z jednej liczby - największej liczby diamentów możliwej do zebrania.

 

Przykład

Wejście:

7 10
0 7 3 0 2 4 8
0 2
0 3
4 6
0 6
6 5
7 1
6 1
2 7
3 2
3 5

Wyjście:

18

ścieżka od jaskini, przez groty 3, 2, 7, 1.

 

Diamenty

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Maciej Szeptuch1011:44:20
2Anna Piekarska1015:38:04
3Wojciech Kuprianowicz1055:29:45
4Karol Kontny1060:01:59
5Darek Bukowski10108:23:58
6Bartek Dudek10137:10:42
7Piotr Strzelecki10346:38:10
8Krzysztof Story10346:46:22
9My My10752:46:24
10Mateusz Wasilewski10944:19:28
11Piotr Jagiełło101620:40:42
12Przemysław Derengowski101932:35:57
13Michal Zgliczynski102359:59:43
14Janusz Wróbel102455:18:53
15Kamil Łukasz103968:59:59
16Maciej Kisiel106074:38:25
17Michał Karpiński108215:38:06
18Szymon Stankiewicz108704:51:10
19Kuba Skałecki108718:39:28
20Jakub Oćwieja109273:20:44
21Łukasz Hanuszczak1010592:08:40
22Kamil Dębowski1011801:06:32
23Karol Farbiś1011963:41:52
24Rafał Wójcik1011965:34:02
25Witold Długosz1013313:11:11
26Agnieszka Dudek9153:25:14
27Jadwiga Andryszak9182:54:28
28Łukasz Hryniuk98632:27:38
29Marek Hołyński99053:00:19
30Rafał Cieślak8877:10:13
31Marcin Skiba84744:18:52
32Przemysław Wawrzyniak412460:34:47
33Kuba Skudlarski287:25:51
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com