警示后人
查看原帖
警示后人
217300
Error_Eric楼主2022/11/16 11:01

本题 Kruskal 重构树的解法是错误的,因为并不是所有对于非 MST 边 (u,v),MST 上 u-v 的路径上所有边权等于 (u,v) 的边都在 kruskal 重构树的 u-v 的路径上。

考虑以下图(边权均为 1,左边原图,右边重构树,A-B-C 是MST,其中A..C 在重构树上的路径不包括(C,D))

             (CD)
             / \
A--B       (AB) D
|  |       / \
|  |    (BC)  A
D--C    / \
        B  C
2022/11/16 11:01
加载中...