D141【LCA最近公共祖先：严格次小生成树】[BJWC2010] 严格次小生成树
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
【题意】
给出一个个点条边的无向连通图，求严格次小生成树。
严格次小生成树：在无向图中，边权和最小的，且满足边权和 严格大于 最小生成树边权和 的生成树。
【输入格式】
第一行两个整数 。
下来 行，每行 个数 表示，点 和点 之间有一条边，边的权值为 。
【输出格式】
一行一个数，表示严格次小生成树的边权和。
【样例输入】
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
【样例输出】
11
【提示】
数据中无向图不保证无自环。
对于 的数据， ，。
对于 的数据， ，。
对于 的数据， ，，边权 ，数据保证必定存在严格次小生成树。
提高8.5（RMQ+最近公共祖先LCA）
- 状态
- 已结束
- 规则
- XCPC
- 题目
- 18
- 开始于
- 2024-8-1 23:00
- 结束于
- 2024-8-10 3:00
- 持续时间
- 196 小时
- 主持人
-
admin
- 参赛人数
- 17