最小树形图 / 朱刘算法
前置定义树形图：在一个有向图中，满足存在一个入度为 $0$ 的点，除了该点入读均为 $1$，且该图不存在环，那么称为树形图。 最小树形图：给定有向边权图，求以某点为根的边权和最小的子图，满足该子图为树形图。朱刘算法模板链接 相当于是一种贪心的思想。 首先我们发现一个合法的树形图中除根外的每个点只有一条入边，所以我们就贪心的选择原图中所有入边中最小的。但是注意到这样选出来的子图可能会存在环，所...
前置定义树形图：在一个有向图中，满足存在一个入度为 $0$ 的点，除了该点入读均为 $1$，且该图不存在环，那么称为树形图。 最小树形图：给定有向边权图，求以某点为根的边权和最小的子图，满足该子图为树形图。朱刘算法模板链接 相当于是一种贪心的思想。 首先我们发现一个合法的树形图中除根外的每个点只有一条入边，所以我们就贪心的选择原图中所有入边中最小的。但是注意到这样选出来的子图可能会存在环，所...