什么是最小树形图 最小树形图就是给定一个$n$个点的有向图,我们钦定一个根,现在要找$n-1$条边,在根能到达其他所有点的前提条件下,使得$n-1$条边的总长度尽可能小。 怎么找最小树形图 这里就得用到朱刘算法了。朱刘算法是一个$O(n \cdot m)$的算法。当然,还有Tarjan巨神的$O(nlogn)$的算法。但我太菜了,并学不会 图出自这里 上面这张图很好的诠释了朱刘算法的主要内容: 我们算法主要有以下几个步骤: 1. 找到到达每个点的长度最小的入边(根节点不找) 2. 这些边如果连成一颗树则结束; 3.…