AT_apc001_d.Forest

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一棵包含 $N$ 个顶点和 $M$ 条边的森林。顶点编号从 $0$ 到 $N-1$ 。每条边以 $(x_i, y_i)$ 的形式给出，表示顶点 $x_i$ 与 $y_i$ 之间有一条边。

每个顶点 $i$ 有一个值 $a_i$ 。你需要通过在给定的森林中添加边，使其变为连通图。每次添加一条边，需要先选择两个不同的顶点（设为 $i$ 和 $j$ ），然后在 $i$ 和 $j$ 之间添加一条边。添加这条边的代价为 $a_i + a_j$ 。注意，添加过边的两个顶点 $i$ 和 $j$ 在之后不能再被选中。

求使该森林连通所需的最小总代价。如果无法连通，输出 Impossible。

输入格式

输入通过标准输入给出，格式如下：

$N\ M$
$a_0\ a_1\ \ldots\ a_{N-1}$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$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
```
输入#2
```
5 0
3 1 4 1 5
```
输出#2
```
Impossible
```
输入#3
```
1 0
5
```
输出#3
```
0
```

说明/提示

限制条件

$1 \leq N \leq 100,\!000$
$0 \leq M \leq N-1$
$1 \leq a_i \leq 10^9$
$0 \leq x_i, y_i < N$
给定的图是森林
输入均为整数

样例解释 1

连接顶点 $0$ 和 $5$ ，图就可以连通，此时的代价是 $1 + 6 = 7$ 。

样例解释 2

无论如何添加边，都无法使图变为连通图。

样例解释 3

图一开始就已经是连通的，因此不需要添加任何边。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页