分数: 466 分
问题陈述
有 N 区域中的城市,编号为 1 to N。城市之间, M 通信电缆已敷设,每根电缆均可双向通信。的 i第电缆 (1 \leq i \leq M) 连接城市 U_i 和城市 V_i,其维护成本为正整数 W_i。该图不包含自环或多重边。
该图是 2-边连接。也就是说,即使其中任何一根电缆 M 电缆被移除,任何两个城市之间仍然可以使用剩余的电缆进行通信。
高桥是该地区的通信管理员,他正试图通过精确选择来构建“骨干网络” N - 1 连接所有城市的电缆。这样的选择 N - 1 电缆对应于生成树。高桥选择电缆时,应尽可能降低主干网络中电缆的总维护成本。换句话说,高桥构建了一个最小生成树。
另一方面,青木是竞争对手公司的工程师。 之前 高桥构建骨干网络,青木可以选择 正是 1 电缆 M 电缆并将其剪断。切断的电缆将变得无法使用并且无法包含在主干网络中。由于该图是 2-边连接,保证无论哪根电缆被切断,仍然可以从剩余的电缆构建生成树 M - 1 电缆。
本游戏流程如下:
- 青木 准确选择 1 电缆 M 电缆并剪断它。
- 高桥 选择 N - 1 剩余电缆 M - 1 以最小的总维护成本(最小生成树)布线并构建生成树。
青木选择要切断的电缆,以便 最大化 总维护成本,预计高桥将构建最小生成树。
请注意,即使存在多个最小生成树,它们的总维护成本也是唯一确定的。因此,一旦青木决定切断哪条电缆,高桥建设的骨干网络的总维护成本也被唯一确定。
求青木最优破坏和高桥最优构建网络时骨干网的总维护成本。
约束
- 3 \leq N \leq 10^5
- N \leq M \leq 2 \times 10^5
- 1 \leq U_i, V_i \leq N
- U_i \neq V_i (无自环)
- If i \neq j,那么 (U_i, V_i) \neq (U_j, V_j) 和 (U_i, V_i) \neq (V_j, U_j) (无多重边)
- 1 \leq W_i \leq 10^9
- W_i 是一个整数
- 该图是 2-边连接(删除任何单边后图仍保持连接)
- 保证答案最多是 2 \times 10^{14}
输入
N M U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
- 第一行包含一个整数 N 代表城市数量和一个整数 M 代表电缆数量,以空格分隔。
- 从第 2 行到 (M + 1)第行,每根电缆的信息都给出了 M 行。
- 的 (1 + i)第行 (1 \leq i \leq M) 包含城市号码 U_i, V_i 认为 i第电缆连接及其维护成本 W_i,用空格分隔。
输出
在单行中以整数形式输出当 Aoki 最优地切断一根电缆并且 Takahashi 构建主干网络以最小化剩余电缆的总维护成本时主干网络的总维护成本。
示例输入 1
3 3 1 2 1 2 3 2 1 3 3
示例输出 1
5
示例输入 2
4 5 1 2 1 2 3 2 3 4 3 4 1 4 1 3 5
示例输出 2
9
示例输入 3
6 9 1 2 3 2 3 5 3 4 2 4 5 7 5 6 1 6 1 4 1 3 8 2 5 6 4 6 9
示例输出 3
20
示例输入 4
8 12 1 2 10 2 3 20 3 4 30 4 5 40 5 6 50 6 7 60 7 8 70 8 1 80 1 5 15 2 6 25 3 7 35 4 8 45
示例输出 4
210
示例输入 5
3 3 1 2 1000000000 2 3 1000000000 1 3 1000000000
示例输出 5
2000000000