kruskar重构树

只略略讲一点基本方式与思想了

  • 构建
    并查集,边按从小(大)到大(小)加入,建新点,点权为此边权,该点为两点根的父亲。

  • 性质:(此处为最小生成树重构树)
    1.lca(u,v)为u到v路径上的最大边权
    2.类似大根堆
    3.显然的性质,叶子为点,非叶子映射边

kruskar重构树

上一篇:二分搜索(常规、左边界、右边界)


下一篇:编译EasyRTC新版本采用ProtocolBuffer(pb)接收不同类型数据如何判断?