| 比赛场次 | 696 |
|---|---|
| 比赛名称 | 2025暑期集训第8场 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2025-08-13 08:00:00 |
| 结束时间 | 2025-08-13 12:00:00 |
| 开放分组 | 全部用户 |
| 组织者 | 梦那边的美好ET |
| 注释介绍 |
| 题目名称 | 次小生成树 |
|---|---|
| 输入输出 | secmst.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 李金泽 |
AAAAAAAAAA | 0.437 s | 15.12 MiB | 100 |
|
左清源 |
AAAAAAAAAA | 0.438 s | 16.78 MiB | 100 |
|
hsl_beat |
AAAAAAAAAA | 0.552 s | 20.03 MiB | 100 |
|
梧叶已同秋雨去 |
AWAAAAAAAA | 0.441 s | 4.42 MiB | 90 |
|
OTTF |
AAAAAAWWAA | 0.770 s | 12.78 MiB | 80 |
|
我也不知道 |
AWAAAAATTT | 7.659 s | 12.03 MiB | 60 |
|
对立猫猫对立 |
AAAAATTTTT | 10.069 s | 7.39 MiB | 50 |
|
xpb |
AAAAATTTTT | 10.171 s | 4.75 MiB | 50 |
|
彭欣越 |
AWAAAEEEEE | 0.767 s | 3.56 MiB | 40 |
|
李奇文 |
AWWWWWWWWW | 0.428 s | 3.68 MiB | 10 |
【题目描述】
小 $C$ 最近学了很多最小生成树的算法，$Prim$ 算法、$Kurskal$ 算法、消圈算法等等。 正当小 $C$ 洋洋得意之时，小 $P$ 又来泼小 $C$ 冷水了。小 $P$ 说，让小 $C$ 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： 如果最小生成树选择的边集是 $E_M$，严格次小生成树选择的边集是 $E_S$，那么需要满足：($value(e)$ 表示边 $e$ 的权值)
这下小 $C$ 蒙了，他找到了你，希望你帮他解决这个问题。大样例
【输入格式】
第一行包含两个整数$N$和$M$，表示无向图的点数与边数。 接下来$M$行，每行$3$个数$x$ $y$ $z$ 表示，点 $x$ 和点 $y$ 之间有一条边，边的权值为 $z$。
【输出格式】
包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)
【样例输入】
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
【样例输出】
11
【提示】
数据中无向图无自环；
$50$% 的数据$N≤2000 , M≤3000$；
$80$% 的数据$N≤5,0000 , M≤10,0000$；
$100$% 的数据$N≤10,0000 , M≤30,0000$ ，边权值非负且不超过 $10^9$。
【来源】
$BZOJ$ $1977$