问题文本中有更正(14:04)
关于该问题还有一条附加说明 (13:25)
問題
背景
在鳗鱼王国,信使鳗鱼很早就被用作通讯手段,但近年来发明了一种神奇的线,可以瞬间传送声音。因此,国王决定用这条神奇的线连接城镇,建立一个通讯网络。由于制作魔线需要时间,所以计划先在关系密切的城镇之间建立群组,只允许群组内部进行交流,然后逐步合并群组,以便在更广阔的范围内进行交流。连接某个群体内的城镇需要一条神奇的线有多长?
課題
頂点数 N ,辺数 M 的无向连通图 给出了 G 。在每个顶点 0 ,..., N-1 数字对应。边的长度为整数。 G 考虑划分上面顶点的组。首先,顶点 假设每个 0 , 1 ,..., N-1(14:04修正) 属于一个仅包含其自身的组。
2 合并两个组以创建新组的“合并查询” 给予 Q 次。对于每个合并查询,选择新合并组中包含的顶点。 仅(于 13:25 添加) 找到使成为长度总和最小的连接所需的边集,并输出该总和。
配点
200
入力
输入按以下格式给出。 输出
N M u1 v1 w1 ... uM vM wM Q p1 q1 ... pQ qQ
N , M 分别表示图的顶点数和边数。继续 M 线表示边缘信息。ui, vi, wi 是顶点ui 和顶点vi之间的长度 表示存在 wi 的边缘。Q表示合并查询的数量。继续 Q 线是一个顶点 包含 pi 的组和顶点 表示包含 qi 的组的合并查询。
制約
输入中的每个变量都满足以下约束。
- 2 \leq N \leq 2,000
- 1 \leq M \leq 200,000 (=2\times 105)
- 0 \leq ui, vi \lt N
- 1 \leq w_i \leq 100,000 (=105)
- 1 \leq Q \lt N
- 0 \leq pi, qi \lt N
- 给定的图是连通的并且不包含多个边或环。
- 已经属于同一组的两个点永远不会作为查询给出。 输出第
出力
输出是 由 Q 行组成。 i 行中,i 次合并查询中合并组连通所需边长之和的最小值。然而,如果这样的一组边不存在,则输出“IMPOSSIBLE”。
入力例1
3 3 0 1 2 0 2 1 1 2 1 2 0 1 1 2
输入示例 1 的输出示例
2 2
最初,每个顶点都属于一个仅包含其自身的组。第一个查询中的顶点 包含 0 的组和顶点 表示包含 1 的组将被合并。合并后的组位于顶部 它由 0 和顶点 连接 1 组成。这个 2 连接两个顶点 1 该边是必需的,且该边的最小长度为 2 。具有以下查询的顶点 1 所属的组和顶点 2 所属的组被合并,并且所有顶点 1 将有两组。使该组相连的边长之和的最小值为 2。
入力例2
5 7 0 1 3 0 4 3 1 2 2 1 3 1 1 4 4 2 3 3 3 4 3 4 0 1 2 4 1 3 3 4
输入示例 2 的输出示例
3 IMPOSSIBLE 4 9