Prim算法坑点

P3366 【模板】最小生成树

gaojizhe05 @ 2024-03-30 19:36:12

如果你用的是 Prim 算法,记得要考虑

重边

试错样例:

输入:

5 18
2 4 276
3 3 435
3 4 608
2 4 860
1 2 318
1 3 547
5 4 419
2 5 98
1 5 460
5 3 399
3 5 240
3 2 733
3 3 903
4 2 909
5 2 206
3 4 810
2 1 115
2 3 419

输出: 729

因为有重边,比如 24 的连边(276 & 680


by George_qwe @ 2024-03-31 17:08:41

orz


|