← 返回题目列表

AtCoder · kupc2017_e

E. 寻宝

中文机器翻译题面 查看原题

分数: 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- 位整数。