d091: P-7-2. 開車蒐集寶物
Tags : DFS 圖論
Accepted rate : 10人/11人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-31 20:00

Content

參加一個蒐集寶物的遊戲,你拿到一個地圖,地圖上有 n 個藏寶點,每個藏寶點有若

干價值的寶物,由於你的團隊是最頂尖的,只要能到達藏寶點一定可以取得該藏寶點

的寶藏。從地圖上看得到一共有 m 條道路,每條道路連接兩個藏寶點,而且每條道路

都是雙向可以通行的。在遊戲的一開始,你可以要求直升機將你的團隊運送到某個藏

寶點,而且你可以獲得一部車與充足的油料,但是直升機的載送只有一次,所以你必

須決定要從哪裡開始才可以獲得最多的寶藏總價值。

Input

第一行是兩個正整數 n 與 m,代表藏寶地點數與道路數,地點是以 0~n-1 編號,第二行 n 個非負整數,依序是每一個地點的寶藏價值,每個地點的寶藏價值

不超過 100。接下來有 m 行,每一行兩個整數 a 與 b 代表一個道路連接的兩個地點

編號。n 不超過 5e4,m 不超過 5e5。兩點之間可能有多條道路,有些道路的兩端點

可能是同一地點。

Output

最大可以獲得的寶藏總價值。

Sample Input
// 1
7 6
5 2 4 2 1 1 8
5 1
1 3
1 4
2 0
2 0
3 3
// 2
3 2
2 1 5
1 0
0 1
Sample Output
// 1
9
// 2
5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
DFS 圖論
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」