最小树形图（朱刘算法）的相关概念

树形图的定义：

1. 以某一个点为根的有向树，被称为 树形图

2. 一个有向图，满足无环且每个点的入度为 $1$ （除了根节点），被称为 树形图

最小树形图： 对于所有树形图中，找到一个总权值和最小的树形图，被称为 最小树形图

最小树形图问题本质上其实就是有向图上的最小生成树问题。Prim 算法和 Kruskal 算法可以解决无向图上的最小生成树问题。朱刘算法可以解决有向图上的最小生成树问题。

朱刘算法

朱刘算法是一个迭代算法，每一次迭代：
1. 除了根节点，对于每个点，找一下这个点的入边中权值最小的边
2. 判断选出的边中是否存在环
$(1)$ 无环，算法结束
$(2)$ 有环，进入步骤 $3$
3. 将所有环缩点，得到新图 $G’$，对于每条边：
$(1)$ 环内部的边，删去
$(2)$ 边的终点 $u$ 在环内，该边的权值变成原权值减去 $u$ 在环内的边的权值，即 $w - w_{环}$
$(3)$ 其他边，不变

算法结束后，之前每一次迭代选出的所有边的总权值之和就是答案。

证明朱刘算法

如果第一次选出的边中不存在环，就意味着当前选出的边满足两个条件，无环且每个点都有一个入边，说明我们选出的是一个树形图，由于每个点选出的边都是所有入边里面权值最小的边，所以一定不可能存在其他方案使得我们选择的边权和更小。

如果有环，那么为什么算法还是对的呢？

假设原图是 $G$，而缩完点且更新完边权之后的图是 $G’$。

我们考虑 $G$ 中任意一个环，由于最终图中一定不能存在环，所以这个环一定存在两个性质，第一点是至少需要去掉一条边，第二点是必然存在一个最优解只去一条边。

假设我们现在任意去掉一条边 $a$，那么必然会选一条新边 $b$ 连向 $a$ 的终点，此时如果我们在任意去掉另外一条边 $c$，那么必然会再选一条新边 $d$ 连向 $c$ 的终点。此时由于 $c$ 一定小于等于 $d$，并且由于去掉了 $a$，选上 $c$ 并不能让图中存在环且权值会变小，因此我们一定可以把 $d$ 换回 $c$。按照这个原理，任意给我们一个最优解，如果最优解中去掉的边数大于 $1$，那么我们必然可以从新加的边去掉，换回环上的边，这样它仍然满足是一个树形图，但是总边权和不会变大。由此得出对于任意一个环，必然存在一个最优解只去一条边。

有了以上两个性质，我们可以进行证明。

假设图 $G$ 中所有环里面只去掉环上一条边的树形图的集合放在左边，将 $G’$ 里面所有树形图的集合放在右边。

对于左边集合中的图的任何一个环，我们只去掉一条边，然后连上一条新边，由于环已经被我们缩点，那么新边就会连向缩点后的新点，对于新点而言，入边就是唯一的，所以去掉一条边后图中无环且每个点的入度为 $1$，所以去掉一条边后会构成一个树形图，说明左边集合的任意一个图，我们都可以转化成右边集合的一个树形图。

反过来，对于右边集合中任意一个树形图，我们找到一个不是根节点的缩点后的点，那么这个点必然存在一个入边，且这个入边必然是原图里的某一条边，且它一定连向缩点后这个点内部的某一个点，我们将这个点对应的内部的边去掉，将这条原图中的边加上。这样可以发现，任给我们一个右边集合的树形图，我们都可以转化成左边集合的一个满足两个性质的树形图。

因此两个集合是相互对应的。

然后看一下数量关系，可以发现左边集合加上了一条环外边 $w$，去掉了一条环内边 $w’$，因此整个操作等于是加上了 $w-w’$，而右边集合中我们定义每条边就是 $w-w’$，所以两个集合在数量关系上也是完全一样的。

综上所述，我们想求左边集合的最小树形图只需要求右边集合的最小树形图就行了，因此每次图中有环进行的处理是正确的。

每次迭代最多去掉一个点，最多迭代 $n$ 次，每次迭代内部是时间复杂度是 $O(m)$，因此整个算法时间复杂度是 $O(nm)$