分数: 200 点
问题陈述
有 n 宝箱和 m 键。
宝箱编号为 1 to n 和宝箱 i 包含一颗有价值的宝石 v_i.
按键编号为 1 to m 和钥匙 i 可以打开任一宝箱 x_i or y_i。 (仅用钥匙无法打开两个宝箱 i.)
你只能得到 1 即使您多次打开同一个宝箱,宝石总数也是如此。
找出您可以获得的珠宝价值的最大总和。
约束
- 所有输入值均为整数。
- 1 \leq n \leq 10^5
- 1 \leq m \leq 2 \times 10^5
- 1 \leq v_i \leq 10^{12} (1 \leq i \leq n)
- 1 \leq x_i, y_i \leq n (1 \leq i \leq m)
输入
输入由标准输入按以下格式给出:
n m v_1 v_2 ... v_n x_1 y_1 x_2 y_2 : x_m y_m
输出
找出您可以获得的珠宝价值的最大总和。
示例输入 1
5 4 20 10 5 8 6 1 2 2 3 3 1 4 5
示例输出 1
43
您可以获得的最大总值 43 如下。
- 使用密钥 1 宝箱 1
- 使用密钥 2 宝箱 2
- 使用密钥 3 宝箱 3
- 使用密钥 4 宝箱 4
示例输入 2
7 4 8 10 9 15 6 3 7 1 7 2 3 3 4 5 6
示例输出 2
39
示例输入 3
10 7 1 9 1 9 1 1 4 5 1 4 1 2 2 3 2 3 3 4 5 6 6 8 7 9
示例输出 3
30
示例输入 4
4 4 20 17 10 1 1 2 1 2 3 3 3 4
示例输出 4
48
多把钥匙可以打开同一套宝箱,有些钥匙只能打开一种宝箱。
示例输入 5
23 20 683654281944 786549938314 108776810532 691131809160 942432243130 63770179509 238399760640 777689878960 646058383313 576573571139 18835030915 479397445387 877859338277 965037937502 199599909896 785875134824 682649947008 167867064215 956377730283 681772713017 633843536114 123843426658 384215401230 4 10 17 19 9 19 20 9 12 19 10 18 13 21 23 19 7 21 11 15 16 19 15 8 8 2 19 10 22 21 14 23 3 19 1 12 6 9 2 10
示例输出 5
11387100771264
输入或输出可能溢出 32- 位整数。