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

最近更新 : 2022-04-08 16:23

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
Sample Output #1
9
Sample Input #2
3 2
2 1 5
1 0
0 1
Sample Output #2
5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
DFS DSU 圖論
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


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