分数: 600 点
问题陈述
你得到了一片森林 N 顶点和 M 边缘。顶点已编号 0 通过 N-1。 边缘以以下格式给出 (x_i,y_i),这意味着顶点 x_i 和 y_i 通过边连接。
每个顶点 i 有一个值 a_i。 您想要在给定的森林中添加边,以便森林相互连接。 要添加边,请选择两个不同的顶点 i 和 j,然后跨过一条边 i 和 j。 此操作成本 a_i + a_j 美元,然后 Vertex 可以再次选择 i 也不 j 。
求使森林连通所需的最低总成本,或打印 Impossible 如果不可能的话。
约束
- 1 ≤ N ≤ 100,000
- 0 ≤ M ≤ N-1
- 1 ≤ a_i ≤ 10^9
- 0 ≤ x_i,y_i ≤ N-1
- 给定的图是一个森林。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
a_0 a_1 .. a_{N-1}
x_1 y_1
x_2 y_2
:
x_M y_M
输出
打印连接森林所需的最低总成本,或打印 Impossible 如果不可能的话。
示例输入 1
7 5 1 2 3 4 5 6 7 3 0 4 0 1 2 1 3 5 6
示例输出 1
7
如果我们连接顶点 0 和 5,图变成连通的,成本为 1 + 6 = 7 美元。
示例输入 2
5 0 3 1 4 1 5
示例输出 2
Impossible
我们无法将图连接起来。
示例输入 3
1 0 5
示例输出 3
0
该图已经连接,因此我们不需要添加任何边。