[AdditionalFile5323.zip](file://AdditionalFile5323.zip?type=additional_file)

#5323. 「EGOI2025」风力涡轮机

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 European Girls' Olympiad in Informatics 2025 Day1 T4. Wind Turbines

Anna 被任务设计北海一个新的海上风力发电场的布线，该风力发电场由 $N$ 个涡轮机组成，编号为 $0, 1, \ldots, N-1$。她的目标是以尽可能低的成本确保所有涡轮机都连接到岸上。

Anna 有一个包含 $M$ 个潜在连接的列表，每个连接链接两个风力涡轮机并具有特定的成本。此外，附近的城市已同意支付将一段连续区间 $[\ell, r]$ 的涡轮机连接到岸上的费用。也就是说，在此范围内的每个涡轮机 $t$ $(\ell \leq t \leq r)$ 都免费直接连接到岸上。如果构建所有潜在连接，则可以从任意一个风力涡轮机到达另一个风力涡轮机。这意味着只要有一个风力涡轮机连接到岸上，就有可能构建连接，使得所有涡轮机的电力都可以传输到岸上。当然，更多的岸上连接可能会降低总成本。请注意，免费连接是唯一直接到岸上的连接。

Anna 的工作是选择潜在连接的一个子集，以最小化其成本总和，同时确保每个风力涡轮机都可以到达岸上（可能通过其他涡轮机）。

为了做出明智的决定，城市为 Anna 提供了 $Q$ 个可能的区间 $[\ell, r]$ 选项。城市要求 Anna 计算每种场景的最小成本。

输入格式

输入的第一行包含三个整数 $N, M, Q$。

接下来的 $M$ 行每行包含三个整数 $u_{i}, v_{i}, c_{i}$。第 $i$ 行描述风力涡轮机 $u_{i}$ 和 $v_{i}$ 之间一个潜在连接，成本为 $c_{i}$。这些连接是无向的，连接两个不同的涡轮机。同一对涡轮机之间不会有两条连接。保证如果构建所有潜在连接，任意一个风力涡轮机都可以直接或间接到达另一个。

接下来的 $Q$ 行每行包含两个整数 $\ell_{i}$ 和 $r_{i}$，描述岸上直接连接到风力涡轮机 $\ell_{i}, \ell_{i}+1, \ldots, r_{i}$ 的场景。注意，当岸上直接连接到单个风力涡轮机时，$r_{i}=\ell_{i}$ 是可能的。

输出格式

输出 $Q$ 行，每行对应一个场景，包含一个整数，表示连接涡轮机使得每个涡轮机都能将其电力传输到岸上的最小成本。

样例 1

输入

5 5 3
1 0 2
0 2 5
1 2 3
3 0 6
2 4 3
1 1
3 4
1 4

输出

14
8
2

在第一个样例中，给出了以下潜在连接图：

我们有三个场景。在第一个场景中，涡轮机 $1$ 是唯一连接到岸上的。在这种情况下，我们需要保留除涡轮机 $0$ 和涡轮机 $2$ 之间的连接之外的所有连接，总成本为 $2+3+6+3=14$。在下一个场景中，涡轮机 $3$ 和 $4$ 连接到岸上。在这种情况下，我们保留连接 $(1,0), (1,2)$ 和 $(2,4)$，成本为 $8$。在第三个场景中，除涡轮机 $0$ 外所有涡轮机都连接到岸上。在这种情况下，我们只需要将这一个连接到另一个涡轮机，我们选择连接 $(0,1)$。各场景的解决方案如下图所示：

第一个样例满足子任务 $2, 5, 7$ 的限制条件。

样例 2

输入

5 4 4
0 1 3
1 2 1
2 3 5
3 4 2
0 4
2 3
2 4
2 2

输出

0
6
4
11

第二个样例满足子任务 $1, 2, 5, 7$ 的限制条件。

样例 3

输入

7 7 4
6 4 3
1 4 5
3 2 4
0 3 2
5 2 3
4 0 1
1 3 1
0 1
2 3
4 5
5 6

输出

12
10
10
10

第三个样例满足子任务 $2, 3, 5, 7$ 的限制条件。

样例 4

输入

7 7 3
2 6 1
1 0 1
0 5 1
1 2 2
3 4 1
5 3 1
5 4 1
5 6
1 3
3 4

输出

5
4
6

第四个样例满足子任务 $2, 4, 5, 7$ 的限制条件。

样例 5

输入

7 7 4
6 4 3
1 4 5
3 2 4
0 3 2
5 2 3
4 0 1
1 3 1
0 3
0 6
0 1
0 4

输出

7
0
12
6

第五个样例满足子任务 $2, 5, 6, 7$ 的限制条件。

样例 6

输入

9 13 4
0 1 1
2 0 3
1 2 4
5 4 4
2 5 6
3 1 7
8 1 4
6 3 9
0 3 5
3 5 3
4 3 2
6 2 4
7 8 5
1 8
4 7
6 7
1 2

输出

1
14
22
24

第六个样例满足子任务 $2, 5, 7$ 的限制条件。

样例 7

输入

6 5 1
0 1 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
1 1

输出

5000000000

第七个样例满足子任务 $1, 2, 5, 7$ 的限制条件。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 100000$。
• $1 \leq M \leq 100000$。
• $1 \leq Q \leq 200000$。
• $0 \leq u_{i}, v_{i} \leq N-1$。
• $u_{i} \neq v_{i}$，且每对风力涡轮机之间最多有一个直接连接。
• $1 \leq c_{i} \leq 1000000000$。
• $0 \leq \ell_{i} \leq r_{i} \leq N-1$。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$8$	$M=N-1$，第 $i$ 个连接有 $u_{i}=i$ 和 $v_{i}=i+1$，即如果构建所有连接，它们形成路径 $0 \leftrightarrow 1 \leftrightarrow 2 \leftrightarrow \ldots \leftrightarrow N-1$
$2$	$11$	$N, M, Q \leq 2000$ 且 $\sum(r_{i} - \ell_{i} + 1) \leq 2000$
$3$	$13$	对于所有 $i$，$r_{i} = \ell_{i} + 1$
$4$	$17$	对于所有 $i$，$1 \leq c_{i} \leq 2$，即每个连接成本为 $1$ 或 $2$
$5$	$16$	$\sum(r_{i} - \ell_{i} + 1) \leq 400000$
$6$	$14$	对于所有 $i$，$\ell_{i} = 0$
$7$	$21$	无附加限制