logo AlgoBeat OnlineJudge
登录 注册

#102238. [BZOJ 2238] Mst

内存限制:256 MiB 时间限制:20000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目描述

给定 $n$ 个点 $m$ 条边的简单无向带权图,$q$ 次询问,询问删掉一条边后图的最小生成树。

询问独立。

输入格式

第一行两个正整数 $n,m$,表示原图的顶点数和边数。

下面 $m$ 行,每行三个整数 $u,v,w$ 描述了图的一条边。保证两点之间至多只有一条边。 接着一行一个正整数 $q$,表示询问数。

下面 $q$ 行,每行一个询问,询问中包含一个正整数 $T$,表示把编号为 $T$ 的边删掉(边从 $1$到 $M$ 按输入顺序编号)。

输出格式

行,对于每个询问输出对应最小生成树的边权和的值,如果图不连通则输出 Not connected

输入输出样例

样例

样例输入 #1

4 4
1 2 3 
1 3 5 
2 3 9 
2 4 1 
4 
1 
2 
3 
4

样例输出 #1

15 
13 
9 
Not connected

数据范围