最小树形图

最小树形图

粗暴地理解就是有向图上的最小生成树。

最小树形图,就是给有向带权图中指定一个特殊的点root,求一棵以root为根的有向生成树T,并且T中所有边的总权值最小。–百毒百科

求取

OI中主流的算法是朱-刘算法